Research ArticleNo Access

Edge domination and 2-independence in trees

Nacéra Meddah

LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

E-mail Address: meddahn11@yahoo.fr

Corresponding author.

Search for more papers by this author

and

Mustapha Chellali

LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

E-mail Address: m_chellali@yahoo.com

Search for more papers by this author

https://doi.org/10.1142/S179355712150159XCited by:0 (Source: Crossref)

Abstract

An edge dominating set in a graph $G = (V, E)$ is a subset $F$ of $E$ such that each edge in $G$ is either in $F$ or adjacent to at least an edge in $F$ . The edge domination number $γ^{'} (G)$ is the minimum cardinality of an edge dominating set in $G$ . A subset $S$ of vertices in $G$ is $2$ -independent if every vertex of $S$ has at most one neighbor in $S .$ The $2$ -independence number $β_{2} (G)$ is the maximum cardinality of a $2$ -independent set of $G .$ We show that if $T$ is a nontrivial tree, then $β_{2} (T) \geq 2 γ^{'} (T)$ and we point out that this inequality is not valid for all bipartite graphs. Moreover, we characterize all trees that achieve equality in this bound.

Communicated by I. Peterin

Keywords:

AMSC: 05C69

References

1. M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, $k$ -domination and $k$ -independence in graphs: A survey, Graphs Combin. 28 (2012) 1–55. Crossref, Web of Science, Google Scholar
2. J. F. Fink and M. S. Jacobson, On $n$ -domination, $n$ -dependence and forbidden subgraphs, in Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985), pp. 301–311. Google Scholar
3. S. R. Jayaram, Line domination in graphs, Graphs Combin. 3 (1987) 357–363. Crossref, Web of Science, Google Scholar
4. S. Mitchell and S. T. Hedetniemi, Edge domination in trees, Congr. Numer. 19 (1977) 489–509. Google Scholar
5. M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38(3) (1980) 364–372. Crossref, Web of Science, Google Scholar