Independence Number and Connectivity of Maximal Connected Domination Vertex Critical Graphs

Almalki, Norah; Kaemawichanurat, Pawaton

doi:10.22049/cco.2023.28629.1639

تعداد نشریات	5
تعداد شماره‌ها	111
تعداد مقالات	1,247
تعداد مشاهده مقاله	1,199,570
تعداد دریافت فایل اصل مقاله	1,060,288

	Independence Number and Connectivity of Maximal Connected Domination Vertex Critical Graphs
Communications in Combinatorics and Optimization
مقاله 1، دوره 9، شماره 2، شهریور 2024، صفحه 185-196 اصل مقاله (451.77 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28629.1639
نویسندگان
Norah Almalki¹؛ Pawaton Kaemawichanurat^* ²^{، 3}
¹Department of Mathematics and Statistics, College of Science, Taif University, Saudi Arabia
²Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology, Thonburi, Thailand
³Mathematics and Statistics with Applications (MaSA), Bangkok, Thailand
چکیده
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.
کلیدواژه‌ها
connected domination؛ independence number؛ connectivity

مراجع
[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
آمار تعداد مشاهده مقاله: 516 تعداد دریافت فایل اصل مقاله: 1,021

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

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

آمار

Independence Number and Connectivity of Maximal Connected Domination Vertex Critical Graphs