Nordhaus-Gaddum type results for connected domination number of graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is called a \textit{dominating set} of $G$ if every vertex not in $S$ is adjacent to some vertex in $S.$ The \textit{domination number} $\gamma(G)$ of $G$ is the minimum cardinality taken over all dominating sets of $G.$ A dominating set $S$ is called a \textit{connected dominating set} if the subgraph induced by $S$ is connected. The minimum cardinality taken over all connected dominating sets of $G$ is called the \textit{connected domination number} of $G,$ and is denoted by $\gamma_c(G).$ In this paper, we investigate the Nordhaus-Gaddum type results for the connected domination number and its derived graphs like line graph, subdivision graph, power graph, block graph and total graph, and characterize the extremal graphs.
Abstract
Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is called a \textit{dominating set} of $G$ if every vertex not in $S$ is adjacent to some vertex in $S.$ The \textit{domination number} $\gamma(G)$ of $G$ is the minimum cardinality taken over all dominating sets of $G.$ A dominating set $S$ is called a \textit{connected dominating set} if the subgraph induced by $S$ is connected. The minimum cardinality taken over all connected dominating sets of $G$ is called the \textit{connected domination number} of $G,$ and is denoted by $\gamma_c(G).$ In this paper, we investigate the Nordhaus-Gaddum type results for the connected domination number and its derived graphs like line graph, subdivision graph, power graph, block graph and total graph, and characterize the extremal graphs.
참고문헌 (23)
- M. Aouchiche, "A survey of Nordhaus-Gaddum type relations", Discrete Applied Mathematics, 161(4-5), pp.466~546 (2013)
- S. Arumugam, "Domination in Subdivision Graphs", Journal of Indian Math Soc, 62(1-4), pp.274~282 (1996)
- S. Arumugam, "Connected Edge Domination in Graphs", Bulletin of the Allahabad Mathematical Society Pramila Srivastava Memorial Volume, 24(1), pp.43~49 (2009)
- M. Behzad, "A criterion for the planarity of a total graph", Proc. Cambridge Philos. Soc, 63, pp.679~681 (1967)
- C. Berge, "Theory of Graphs and Its Applications" (1962), Hethuen
- J. A. Bondy, "Graph Theory" (2008), Spinger
- M. B. Cozzens, "Dominating cliques in graphs", Discrete Math, 86, pp.145~164 (1990)
- Frank Harary, "Graph Theory" (1969), Addison-Wesley Publishing Company
- Gary Chartrand, "Introduction To Graph Theory" (2006), Tata McGraw-Hill
- T. W. Haynes, "Fundamentals of domination in graphs" (1998), Marcel Dekkar, Inc
- S. T. Hedetniemi, "Graph Theory and Combinatorics", pp.209~218 (1984), Academic Press
- F. Jaeger, "Relations due Type Nordhaus-Gaddum pour le Nombre d’Absorption d’un Graphe Simple", C. R. Acad. Sci. Paris Ser. A, 274, pp.728~730 (1972)
- B. S. Karunagaram, "On Domination Parameters and Maximum Degree of a Graph", Journal of Discrete Mathematical Sciences & Cryptography, 9(2), pp.215~223 (2006)
- G. Mahadevan, "Complementary Triple Connected Domination Number of a Graph", Advances and Applications in Discrete Mathematics, 12(1), pp.39~54 (2013)
- Moo Young Sohn, "Classification of Regular Planar Graphs with Diameter Two, Acta Mathematica Sinica", English Series, 23(3), pp.411~416 (2007)
- E. Murugan, "On the domination number of a graph and its line graph", International Journal of Mathematical Combinatorics, (1), pp.170~181 (2018)
- E. Murugan, "On the Domination Number of a Graph and its Total Graph, Discrete Mathematics", Algorithms and Applications, 12(5), pp.2050068~ (2020)
- E. Murugan, "On the Domination Number of a Graph and its Shadow Graph, Discrete Mathematics", Algorithms and Applications, 13(6), pp.2150074~ (2021)
- E. Murugan, "On the Domination Number of a Graph and its Block Graph, Discrete Mathematics", Algorithms and Applications, 14(7), pp.2250033~ (2022)
- E. A. Nordhaus, "On complementary graphs", Amer. Math. Monthly, 63, pp.177~182 (1956)
- O. Ore, "Theory of Graphs", Math. SOC. Colloq. Publ, 38 (1962)
- E. Sampathkumar, "The connected domination number of a graph", J. Math. Phys. Sci, 13, pp.607~613 (1979)
- W. J. Desormeaux, "Bounds on the connected domination number of a graph", Discrete Applied Mathematics, 161, pp.2925~2931 (2013)