Domination and irredundance in cubic graphs (Q1356461): Difference between revisions
From MaRDI portal
Latest revision as of 10:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Domination and irredundance in cubic graphs |
scientific article |
Statements
Domination and irredundance in cubic graphs (English)
0 references
29 October 1997
0 references
This paper shows that for every positive integer \(k\) there exists a connected cubic graph \(H_k\) whose upper irredundance number \(\text{IR}(H_k)\) and upper dominating number \(\Gamma(H_k)\) satisfies \(\text{IR}(H_k)-\Gamma(H_k)\geq k\), thus disproving a conjecture of Henning and Slater, and that if \(G\) is regular, \(\text{IR}(G)\leq{1\over 2}n\). In both cases the extremal graphs are characterized and shown to satisfy \(\Gamma(G)=\text{IR}(G)\).
0 references
cubic graph
0 references
irredundance number
0 references
dominating number
0 references
extremal graphs
0 references
0 references