On the total domatic number of regular graphs

Aram, H.; Sheikholeslami, S. M.; Volkmann, L.

doi:10.22108/toc.2012.760

تعداد نشریات	43
تعداد شماره‌ها	1,682
تعداد مقالات	13,778
تعداد مشاهده مقاله	32,290,006
تعداد دریافت فایل اصل مقاله	12,769,362

	On the total domatic number of regular graphs
Transactions on Combinatorics
مقاله 7، دوره 1، شماره 1، خرداد 2012، صفحه 45-51 اصل مقاله (265.23 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2012.760
نویسندگان
H. Aram¹؛ S. M. Sheikholeslami^* ¹؛ L. Volkmann²
¹Azarbaijan University of Tarbiat Moallem
²RWTH-Aachen University
چکیده
‎A set $S$ of vertices of a graph $G=(V,E)$ without isolated vertex‎ ‎is a total dominating set if every vertex of $V(G)$ is‎ ‎adjacent to some vertex in $S$‎. ‎The total domatic number of‎ ‎a graph $G$ is the maximum number of total dominating sets into‎ ‎which the vertex set of $G$ can be partitioned‎. ‎We show that the‎ ‎total domatic number of a random $r$-regular graph is almost‎ ‎surely at most $r-1$‎, ‎and that for 3-regular random graphs‎, ‎the‎ ‎total domatic number is almost surely equal to 2‎. ‎We also give a‎ ‎lower bound on the total domatic number of a graph in terms of‎ ‎order‎, ‎minimum degree and maximum degree‎. ‎As a corollary‎, ‎we‎ ‎obtain the result that the total domatic number of an $r$-regular‎ ‎graph is at least $r/(3\ln(r))$‎.
کلیدواژه‌ها
total dominating set؛ total domination number؛ total domatic number؛ Regular graph

مراجع
N. Alon (1990) Transversal numbers of uniform hypergraphs Graphs Combin. 6, 1-4 S. Arumugam and A. Thuraiswamy (1998) Total domatic number of a graph Indian J. Pure Appl. Math. 29, 513-515 E. A. Bender and E. R. Canfield (1978) The asymptotic number of labeled graphs with given degree sequences J. Combin. Theory Ser. A 24, 296-307 I. Bouchemakh and S. Ouatiki (2009) On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset Discrete Math. 309, 3674-3679 E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi (1980) Total domination in graphs Networks 10, 211-219 P. Dankelmann, N. J. Calkin (2004) The Domatic Number of Regular Graphs Ars Combin. 73, 247-255 T. W. Haynes, S. T. Hedetniemi, P. J. Slater (1998) Fundamentals of Domination in Graphs Marcel Dekker, Inc., New York T. W. Haynes, S. T. Hedetniemi, P. J. Slater, editors (1998) Domination in Graphs, Advanced Topics Marcel Dekker, Inc., New York D. B. West (2000) Introduction to Graph Theory Prentice-Hall, Inc N. C. Wormald (1999) Models of Random Regular Graphs In: Surveys in Combinatorics 1999 (J.D. Lamb and D.A. Preece, eds.), London Mathematical Society Lecture Notes Series , Cambridge University Press, Cambridge 267, 239-298 B. Zelinka (1988) Total domatic number of cacti Math. Slovaca 38, 207-214 B. Zelinka (1989) Total domatic number and degrees of vertices of a graph Math. Slovaca 39, 7-11
آمار تعداد مشاهده مقاله: 5,743 تعداد دریافت فایل اصل مقاله: 3,767

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

On the total domatic number of regular graphs