On the domination number of a graph and its square graph
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For a given graph $G=(V, E),$ a dominating set is a subset $V'$ of the vertex set $V$ so that each vertex in $V \setminus V'$ is adjacent to a vertex in $V'.$ The minimum cardinality of a dominating set of $G$ is called the \textit{domination number} of $G$ and is denoted by $\gamma(G).$ For an integer $k \geq 1,$ the \textit{k-th power} $G^k$ of a graph $G$ with $V(G^k)=V(G)$ for which $uv \in E(G^k)$ if and only if $1 \leq d_{G}(u,v) \leq k.$ Note that $G^2$ is the square graph of a graph $G.$ In this paper, we obtain some tight bounds for the sum of the domination numbers of a graph and its square graph in terms of the order, order and size, and maximum degree of the graph $G.$ Also, we characterize such extremal graphs.
Abstract
For a given graph $G=(V, E),$ a dominating set is a subset $V'$ of the vertex set $V$ so that each vertex in $V \setminus V'$ is adjacent to a vertex in $V'.$ The minimum cardinality of a dominating set of $G$ is called the \textit{domination number} of $G$ and is denoted by $\gamma(G).$ For an integer $k \geq 1,$ the \textit{k-th power} $G^k$ of a graph $G$ with $V(G^k)=V(G)$ for which $uv \in E(G^k)$ if and only if $1 \leq d_{G}(u,v) \leq k.$ Note that $G^2$ is the square graph of a graph $G.$ In this paper, we obtain some tight bounds for the sum of the domination numbers of a graph and its square graph in terms of the order, order and size, and maximum degree of the graph $G.$ Also, we characterize such extremal graphs.
참고문헌 (19)
- M. Aouchiche, "A survey of Nordhaus-Gaddum type relations", Discrete Applied Mathematics, 161(4-5), pp.466~546 (2013)
- C. Berge, "Theory of Graphs and Its Applications" (1962), Hethuen
- J. A. Bondy, "Graph Theory" (2008), Spinger
- E. J. Cockayne, "Extremal graphs for inequalities involving domination parameters", Discrete. Math, 216, pp.1~10 (2000)
- J. F. Frank, "On graphs having domination number half their order", Period. Math. Hungar, 16, pp.287~293
- W. Goddard, "Domination in planar graphs with small diameter", J. Graph Theory, 40, pp.1~25 (2002)
- T. W. Haynes, "Fundamentals of domination in graphs" (1998), Marcel Dekkar, Inc
- 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)
- G. MacGillivray, "Domination numbers of planar graphs", J. Graph Theory, 22, pp.213~229 (1996)
- 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, (Special Issue 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 (2021)
- E. A. Nordhaus, "On complementary graphs", Amer. Math. Monthly, 63, pp.177~182 (1956)
- O. Ore, "Theory of Graphs" (1962)
- C. Payan, "Domination-balanced graphs", J. Graph Theory, 6, pp.23~32 (1982)
- B. Randerath, "Characterization of graphs with equal domination and covering number", Discrete. Math, 191, pp.173~179 (1998)
- H. B. Walikar, "MRI Lecture Notes in Math" (1979), Mahta Research Instit