Independence Number and Connectivity of Maximal Connected Domination Vertex Critical Graphs

Document Type : Original paper

Authors

1 Department of Mathematics and Statistics, College of Science, Taif University, Saudi Arabia

2 Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology, Thonburi, Thailand

3 Mathematics and Statistics with Applications (MaSA), Bangkok, Thailand

Abstract

A $k$-CEC graph is a graph $G$ which has connected domination number $\gamma_{c}(G) = k$ and $\gamma_{c}(G + uv) < k$ for every $uv \in E(\overline{G})$. A $k$-CVC graph $G$ is a $2$-connected graph with  $\gamma_{c}(G) = k$ and $\gamma_{c}(G - v) < k$ for any $v \in V(G)$. A graph is said to be maximal $k$-CVC if it is both $k$-CEC and $k$-CVC. Let $\delta$, $\kappa$, and $\alpha$ be the minimum degree, connectivity, and independence number of $G$, respectively. In this work, we prove that for a maximal $3$-CVC graph, if $\alpha = \kappa$, then $\kappa = \delta$. We additionally consider the class of maximal $3$-CVC graphs with $\alpha < \kappa$ and $\kappa < \delta$, and prove that every $3$-connected maximal $3$-CVC graph when $\kappa < \delta$ is Hamiltonian connected.

Keywords

Main Subjects

References

[1] N. Ananchuen, On domination critical graphs with cut vertices having connected domination number 3, Int. Math. Forum, vol. 2, Citeseer, 2007, pp. 3041–3052.
[2] W. Ananchuen, N. Ananchuen, and M.D. Plummer, Vertex criticality for connected domination, Util. Math. 86 (2011), 45--64.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008.
[4] X. Chen, L. Sun, and D. Ma, Connected domination critical graphs, Appl. Math. Lett. 17 (2004), no. 5, 503–507. https://doi.org/10.1016/S0893-9659(04)90118-8
[5] V. Chvátal and P. Erdös, A note on hamiltonian circuits, Discrete Math. 2 (1972), no. 2, 111–113. https://doi.org/10.1016/0012-365X(72)90079-9
[6] P. Kaemawichanurat, On the independence number of 3-cec graphs, Manuscript.
[7] P. Kaemawichanurat, Connected domination critical graphs, Ph.D. thesis, Curtin University, 2015.
[8] P. Kaemawichanurat and L. Caccetta, Independence and connectivity of connected domination critical graphs, arXiv preprint arXiv:1911.04961 (2019).
[9] P. Kaemawichanurat, L. Caccetta, and W. Ananchuen, Hamiltonicity of connected domination critical graphs, Ars Combin. 136 (2018), 127–151.
[10] J. Simmons, Closure operations and hamiltonian properties of independent and total domination critical graphs, Ph.D. thesis, University of Victoria, 2005.
[11] L. Zhang and F. Tian, Independence and connectivity in 3-domination-critical graphs, Discrete Math. 259 (2002), no. 1-3, 227–236. https://doi.org/10.1016/S0012-365X(02)00383-7
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 185-196

Files

Share

How to cite

Statistics