×

Common extremal graphs for three inequalities involving domination parameters. (English) Zbl 1463.05421

Summary: Let \(\delta (G)\), \(\Delta (G)\) and \(\gamma(G)\) be the minimum degree, maximum degree and domination number of a graph \(G=(V(G), E(G))\), respectively. A partition of \(V(G)\), all of whose classes are dominating sets in \(G\), is called a domatic partition of \(G\). The maximum number of classes of a domatic partition of \(G\) is called the domatic number of \(G\), denoted \(d(G)\). It is well known that \(d(G) \leq \delta(G) + 1\), \(d(G) \gamma(G) \leq |V(G)|\) [E. J. Cockayne and S. T. Hedetniemi, Networks 7, 247–261 (1977; Zbl 0384.05051)], and \(|V(G)| \leq (\Delta(G)+1) \gamma(G)\) [C. Berge, Graphs and hypergraphs. Amsterdam-London: North-Holland Publishing Company; New York: American Elsevier Publishing Company, Inc. (1973; Zbl 0254.05101)]. In this paper, we investigate the graphs \(G\) for which all the above inequalities become simultaneously equalities.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. W. Bange, A. E. Barkauskas and P. J. Slater, Efficient Dominating Sets in Graphs, SIAM, Philadelphia, 1988, 189-199. · Zbl 0664.05027
[2] M. A. Bonucelli, Dominating sets and domatic number of circular arc graphs,Discrete Appl. Math.,12(1985) 203-213. · Zbl 0579.05051
[3] C. Berge,Graphs and Hypergraphs, North-Holland, Amsterdam, 1973. · Zbl 0254.05101
[4] E. J. Cockayne,Domination in undirected graphs - a survey, Springer-Verlag, Berlin, 1978, 141-147. · Zbl 0384.05052
[5] E. J. Cockayne and S. T. Hedetniemi, Disjoint independent dominating sets in graphs,Discrete Math.,15(1976) 213-222. · Zbl 0364.05035
[6] E. J. Cockayne and S. T. Hedetniemi, Towards a Theory of Domination in Graphs,Networks,7(1977) 247-261 · Zbl 0384.05051
[7] M. Farber, Domination, idependent domination, and duality in strongly chordal graph,Discrere Appl. Math.,7(1984) 115-130 · Zbl 0531.05045
[8] S. Fujita, M. Yamashita and T. Kameda, A study onr-configurations – a resource assignment problem on graphs,SIAM J. Disc. Math.,13(2000) 227-254. · Zbl 0941.05050
[9] T. W. Haynes, S. T. Hedetniemi and P. J. Slater,Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. · Zbl 0890.05002
[10] T. W. Haynes, L. M. Lawson, R. C. Brigham and R. D. Dutton, Changing and unchanging of the graphical invariants: minimum and maximum degree, maximum clique sizes, node independence number and edge independence number, Congr. numer.,72(1990) 239-252 · Zbl 0696.05029
[11] J. Huang, J.-M. Xu The bondage numbers and efficient dominations of vertex-transitive graphs,Discrete Math.,308 (2008) 571-582 · Zbl 1130.05043
[12] B. J. Ebrahimi, N. Jahanbakht, E. S. Mahmoodian, Vertex domination of generalized Petersen graphs,Discrete Math., 309(2009) 4355-4361 · Zbl 1181.05066
[13] M. Mollard, On perfect codes in Cartesian products of graphs,Europ. J. Combin.,32(2011) 398-403 · Zbl 1209.05207
[14] A. Srinivas Rao and C. Pandu Rangan, A linear algorithm for domatic number of interval graphs,Inform. Process. Lett.,33(1989-90) 29-33. · Zbl 0685.68062
[15] M. Valencia-Pabon, Idomatic partitions of direct products of complete graphs,Discrete Math.,310(2010) 1118-1122. · Zbl 1215.05136
[16] B. Zelinka, Domatically critical graphs,Czechoslovak Math. J.,30(1980) 486-489. · Zbl 0426.05046
[17] B. Zelinka, On two problems of the graph theory,Casopis pro pˇˇestov´ani matematiky,107(1982) 109-113 · Zbl 0492.05058
[18] B. Zelinka, Adomatic and idomatic numbers of graphs,Math. Slovaca,33(1983) 99-103 Vladimir Samodivkin Department of Mathematics, UACEG, P.O.Box 1164, Sofia, Bulgaria Email:vl.samodivkin@gmail.com · Zbl 0507.05059
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.