On the relations between the parameters of graphs

Two elements (vertices or edges) of a graph \(G\) are dependent if they are either adjacent or incident; otherwise they are independent. The paper establishes some relations between the dominating number \(\sigma(G)\), edge dominating number \(\sigma_1(G)\), total covering number \(\alpha_T(G)\), total independence number \(\beta_T(G)\), and order \(p\) of \(G\). Let \(\delta(G)\) be the minimum degree of \(G\) and \(\overline{G}\) denote the complement of \(G\). The results: (1) \(\sigma(G)+\beta_T(G)\leq p+\lfloor \frac{p}{4}\rfloor\) if \(\delta(G)>0\), (2) \(\sigma_1(G)+\beta_T(G)=p\), (3) \(\sigma(G)+\alpha_T(G)\leq p \) if \(\delta(G)>0\), (4) \(\sigma_1(G)+\alpha_T(G)\leq p\), (5) \(\lceil\frac{p+3}{2}\rceil\leq \sigma(\overline{G})+\beta_T(G)\leq \lceil\frac{3p}{2}\rceil\), (6) \(\lceil\frac{p}{2}\rceil\leq \sigma_1(\overline{G})+\beta_T(G)\leq \lfloor\frac{3p}{2}\rfloor\), (7) \(\sigma(\overline{G})+\alpha_T(G)\leq \lceil\frac{3p}{2}\rceil\), and (8) \(\lceil\frac{p}{2}\rceil\leq \sigma_1(\overline{G})+\alpha_T(G)\leq \lfloor\frac{3p}{2}\rfloor\). Moreover, all these bounds are sharp.

Recommendations

Cited in

(12)

This page was built for publication: On the relations between the parameters of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372398)