پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,731,468 |
| تعداد دریافت فایل اصل مقاله | 17,563,680 |
Common extremal graphs for three inequalities involving domination parameters | ||
| Transactions on Combinatorics | ||
| مقاله 1، دوره 6، شماره 3، آذر 2017، صفحه 1-9 اصل مقاله (243.24 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2017.21464 | ||
| نویسنده | ||
| Vladimir Samodivkin* | ||
| University of Architecture, Civil Engineering and Geodesy (UACEG) | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| domination/domatic/idomatic number؛ efficient dominating set | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 895 تعداد دریافت فایل اصل مقاله: 637 |
||