Bulletin of the Korean Mathematical Society (대한수학회보)

Korean Mathematical Society (대한수학회)
권호 표지
DOI QR코드

DOI QR Code

TOTAL DOMINATION NUMBER OF CENTRAL GRAPHS

  • Received : 2018.09.19
  • Accepted : 2019.03.04
  • Published : 2019.07.31
Download PDF
⟨ Previous Next ⟩

Abstract

Let G be a graph with no isolated vertex. A total dominating set, abbreviated TDS of G is a subset S of vertices of G such that every vertex of G is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a TDS of G. In this paper, we study the total domination number of central graphs. Indeed, we obtain some tight bounds for the total domination number of a central graph C(G) in terms of some invariants of the graph G. Also we characterize the total domination number of the central graph of some families of graphs such as path graphs, cycle graphs, wheel graphs, complete graphs and complete multipartite graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the total domination number of central graphs.

Keywords

E1BMAX_2019_v56n4_1059_f0001.png 이미지

FIGURE 1. A min-TDS of C(P7)

E1BMAX_2019_v56n4_1059_f0002.png 이미지

FIGURE 2. A min-TDS of C(C7)

E1BMAX_2019_v56n4_1059_f0003.png 이미지

FIGURE 3. A min-TDS of C(K3,4)

E1BMAX_2019_v56n4_1059_f0004.png 이미지

FIGURE 4. A min-TDS of C(K2,2,3)

E1BMAX_2019_v56n4_1059_f0005.png 이미지

FIGURE 5. A min-TDS of C(P4 ◦ P1)

E1BMAX_2019_v56n4_1059_f0006.png 이미지

FIGURE 6. A min-TDS of C(S1,3,3)

E1BMAX_2019_v56n4_1059_f0007.png 이미지

FIGURE 7. A min-TDS of C(W6)

References

  1. G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw-Hill, Kalamazoo, MI, 2004,
  2. E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211-219. https://doi.org/10.1002/net.3230100304
  3. M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, New York, 2013. https://doi.org/10.1007/978-1-4614-6525-6
  4. E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956), 175-177. https://doi.org/10.2307/2306658
  5. J. V. Vernold, Harmonious coloring of total graphs, n-leaf, central graphs and circumdetic graphs, Ph.D Thesis, Bharathiar University, Coimbatore, India, 2007.
  6. D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.