Narrow Results

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 ${\gamma }^{\prime }(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 ${\beta }_2(G)$ is the maximum cardinality of a $2$-independent set of $G.$ We show that if $T$ is a nontrivial tree, then ${\beta }_2(T)\ge 2{\gamma }^{\prime }(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.

In a graph, an edge dominates itself and all its adjacent edges. An edge dominating set (EDS) in a graph $G$ is a subset of edges that dominates every edge of $G.$ In this paper, we characterize edges that are in all or in no minimum EDS in trees.