Domination and irredundance in cubic graphs
type: Item
instance of: scholarly article
title: Domination and irredundance in cubic graphs
zbMATH Open document ID: 0873.05056
DOI: 10.1016/S0012-365X(96)00229-4
author: E. J. Cockayne
author: Christina M. Mynhardt
published in: Discrete Mathematics
publication date: 1997-10-29T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1018515
zbMATH Keywords: cubic graph
zbMATH Keywords: irredundance number
zbMATH Keywords: dominating number
zbMATH Keywords: extremal graphs
MaRDI profile type: Publication
cites work: On domination and independent domination numbers of a graph
cites work: What is the difference between the domination and independent domination numbers of a cubic graph?
cites work: Q3941433
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Q3987051
cites work: Stability, domination and irredundance in a graph
cites work: Two relations between the parameters of independence and irredundance
cites work: Inequalities relating domination parameters in cubic graphs
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: A note on graphs which have upper irredundance equal to independence
cites work: Q3206969
cites work: Q4873765
cites work: A counterexample to conjecture of Barefoot, Harary, and Jones
full work available at URL: s0012-365x(96)00229-4
OpenAlex ID: W2056606203
description: scientific article; zbMATH DE number 1018515