Common extremal graphs for three inequalities involving domination parameters

Document Type : Research Paper

Author

University of Architecture, Civil Engineering and Geodesy (UACEG)

Abstract

‎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)|$ \cite{ch}‎, ‎and $|V(G)| \leq (\Delta(G)‎+‎1)\gamma(G)$ \cite{berge}‎. ‎In this paper‎, ‎we investigate the graphs $G$ for which‎ ‎all the above inequalities become simultaneously equalities‎.

Keywords

Main Subjects

References

[1] D. W. Bange, A. E. Barkauskas and P. J. Slater, Efficient Dominating Sets in Graphs, SIAM, Philadelphia, 1988, 189-199.
[2] M. A. Bonucelli, Dominating sets and domatic numb er of circular arc graphs, Discrete Appl. Math., 12 (1985) 203-213.
[3] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
[4] E. J. Co ckayne, Domination in undirected graphs-a survey, Springer-Verlag, Berlin, 1978, 141-147.
[5] E. J. Co ckayne and S. T. Hedetniemi, Disjoint indep endent dominating sets in graphs, Discrete Math., 15 (1976) 213-222.
[6] E. J. Co ckayne and S. T. Hedetniemi, Towards a Theory of Domination in Graphs, Networks, 7 (1977) 247-261.
[7] M. Farb er, Domination, idep endent domination, and duality in strongly chordal graph, Discrere Appl. Math., 7 (1984) 115-130.
[8] S. Fujita, M. Yamashita and T. Kameda, A study on r -con gurations { a resource assignment problem on graphs, SIAM J. Disc. Math., 13 (2000) 227-254.
[9] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[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, no de indep endence numb er and edge indep endence numb er, Congr. numer., 72 (1990) 239-252.
[11] J. Huang, J.-M. Xu The b ondage numb ers and efficient dominations of vertex-transitive graphs, Discrete Math., 308 (2008) 571-582.
[12] B. J. Ebrahimi, N. Jahanbakht, E. S. Mahmo o dian, Vertex domination of generalized Petersen graphs, Discrete Math., 309 (2009) 4355-4361.
[13] M. Mollard, On p erfect co des in Cartesian pro ducts of graphs, Europ. J. Combin., 32 (2011) 398-403.
[14] A. Srinivas Rao and C. Pandu Rangan, A linear algorithm for domatic numb er of interval graphs, Inform. Process. Lett., 33 (1989-90) 29-33.
[15] M. Valencia-Pab on, Idomatic partitions of direct pro ducts of complete graphs, Discrete Math., 310 (2010) 1118-1122.
[16] B. Zelinka, Domatically critical graphs, Czechoslovak Math. J., 30 (1980) 486-489.
[17] B. Zelinka, On two problems of the graph theory, Casopis pro pestovani matematiky, 107 (1982) 109-113.
[18] B. Zelinka, Adomatic and idomatic numb ers of graphs, Math. Slovaca, 33 (1983) 99-103.
Transactions on Combinatorics
Volume 6, Issue 3 - Serial Number 3
September 2017
Pages 1-9

Files

History

  • Receive Date: 26 January 2017
  • Revise Date: 15 May 2017
  • Accept Date: 15 May 2017
  • Published Online: 01 September 2017

Share

How to cite

Statistics