On the relations between the parameters of graphs (Q2372398): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 18:15, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the relations between the parameters of graphs |
scientific article |
Statements
On the relations between the parameters of graphs (English)
0 references
26 July 2007
0 references
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.
0 references
dominating number
0 references
edge dominating number
0 references
total independence number
0 references
total covering number
0 references