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.

A Roman dominating function (RDF) on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ of $G$ for which $f(v)=2$. The weight of a RDF is the sum $f(V)={\sum }_{v\in V}f(v)$, and the minimum weight of a RDF $f$ is the Roman domination number ${\gamma }_R(G)$. A subset $S$ of $V$ is a $2$-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S.$ The maximum cardinality of a $2$-independent set of $G$ is the $2$-independence number ${\beta }_2(G).$ Both parameters are incomparable in general, however, we show that if $T$ is a tree, then ${\beta }_2(T)\ge {\gamma }_R(T)$. Moreover, all extremal trees attaining equality are characterized.