×

Inequalities relating domination parameters in cubic graphs. (English) Zbl 0858.05058

The paper presents various inequalities for numerical invariants of graphs \(G\) which concern domination. The following invariants are considered: domination number \(\gamma(G)\), upper domination number \(\Gamma(G)\), irredundance number \(\text{ir}(G)\), upper irredundance number \(\text{IR}(G)\), independent domination number \(i(G)\), independence number \(\beta_0(G)\), minus domination number \(\gamma^-(G)\), and signed domination number \(\gamma_s(G)\). The inequalities concern cubic graphs, i.e. regular graphs of degree 3.

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. Barefoot, F. Harary and K.F. Jones, What is the difference between α and \(α^1\); C. Barefoot, F. Harary and K.F. Jones, What is the difference between α and \(α^1\) · Zbl 0728.05033
[2] Cockayne, E. J.; Favaron, O.; Payan, C.; Thomason, A., Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math., 33, 249-258 (1981) · Zbl 0471.05051
[3] Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21, 4, 461-468 (1978) · Zbl 0393.05044
[4] Cockayne, E. J.; Mynhardt, C. M., Independence and domination in 3-connected cubic graphs, J. Combin. Math. Combin. Comput., 10, 173-182 (1991) · Zbl 0763.05094
[5] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and A.A. McRae, Minus domination in graphs, submitted.; J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and A.A. McRae, Minus domination in graphs, submitted. · Zbl 0928.05046
[6] Dunbar, J. E.; Hedetniemi, S. T.; Henning, M. A.; Slater, P. J., Signed domination in graphs, (Graph Theory, Combinatorics and Applications (1995), Wiley: Wiley New York), 311-322 · Zbl 0842.05051
[7] S.T. Hedetniemi, private communication.; S.T. Hedetniemi, private communication.
[8] M.A. Henning, Domination in regular graphs. Ars Combin., to appear.; M.A. Henning, Domination in regular graphs. Ars Combin., to appear. · Zbl 0881.05101
[9] Jacobson, M. S.; Peters, K., Chordal graphs and upper irredundance, upper domination and independence, Discrete Math., 86, 59-69 (1990) · Zbl 0744.05063
[10] Mynhardt, C. M., On the difference between the domination and independent domination numbers of cubic graphs, (Graph Theory, Combinatorics and Applications, Vol. 2 (1991), Wiley: Wiley New York), 939-947 · Zbl 0840.05038
[11] Zelinka, B., Domination in cubic graphs, (Topics in Combinatorics and Graph Theory (1990), Physica-Verlag: Physica-Verlag Heidelberg), 727-735 · Zbl 0745.05064
[12] Zelinka, B., Some remarks on domination in cubic graphs, Discrete Math., 158, 249-255 (1996), (this Vol.) · Zbl 0861.05034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.