The existence of a graph whose vertex set can be partitioned into a fixed number of strong domination-critical vertex-sets

Weisheng Zhao; Ying Li; Ruizhi Lin; Weisheng Zhao; Ying Li; Ruizhi Lin

doi:10.3934/math.2024095

AIMS Mathematics

2024, Volume 9, Issue 1: 1926-1938. doi: 10.3934/math.2024095

Previous Article Next Article

Research article Special Issues

The existence of a graph whose vertex set can be partitioned into a fixed number of strong domination-critical vertex-sets

1.
School of Artificial Intelligence, Jianghan University, Wuhan, Hubei 430056, China
2.
Institute for Interdisciplinary Research, Jianghan University, Wuhan, Hubei 430056, China
3.
School of Computer Science and Mathematics, Fujian University of Technology, Fuzhou, Fujian 350118, China

Received: 19 September 2023 Revised: 17 November 2023 Accepted: 04 December 2023 Published: 18 December 2023
MSC : 05C69

Let $ \gamma(G) $ denote the domination number of a graph $ G $. A vertex $ v\in V(G) $ is called a critical vertex of $ G $ if $ \gamma(G-v) = \gamma(G)-1 $. A graph is called vertex-critical if its every vertex is critical. In this paper, we correspondingly introduce two such definitions: (i) A set $ S\subseteq V(G) $ is called a strong critical vertex-set of $ G $ if $ \gamma(G-S) = \gamma(G)-|S| $; (ii) A graph $ G $ is called strong $ l $-vertex-set-critical if $ V(G) $ can be partitioned into $ l $ strong critical vertex-sets of $ G $. Therefrom, we give some properties of strong $ l $-vertex-set-critical graphs by extending the previous results of vertex-critical graphs. As the core work, we study on the existence of this class of graphs and prove that there exists a strong $ l $-vertex-set-critical connected graph if and only if $ l\notin\{2, 3, 5\} $.
- domination,
- critical vertex,
- strong critical vertex-set,
- vertex-critical graph
Citation: Weisheng Zhao, Ying Li, Ruizhi Lin. The existence of a graph whose vertex set can be partitioned into a fixed number of strong domination-critical vertex-sets[J]. AIMS Mathematics, 2024, 9(1): 1926-1938. doi: 10.3934/math.2024095

Related Papers:

Abstract

Let $ \gamma(G) $ denote the domination number of a graph $ G $. A vertex $ v\in V(G) $ is called a critical vertex of $ G $ if $ \gamma(G-v) = \gamma(G)-1 $. A graph is called vertex-critical if its every vertex is critical. In this paper, we correspondingly introduce two such definitions: (i) A set $ S\subseteq V(G) $ is called a strong critical vertex-set of $ G $ if $ \gamma(G-S) = \gamma(G)-|S| $; (ii) A graph $ G $ is called strong $ l $-vertex-set-critical if $ V(G) $ can be partitioned into $ l $ strong critical vertex-sets of $ G $. Therefrom, we give some properties of strong $ l $-vertex-set-critical graphs by extending the previous results of vertex-critical graphs. As the core work, we study on the existence of this class of graphs and prove that there exists a strong $ l $-vertex-set-critical connected graph if and only if $ l\notin\{2, 3, 5\} $.

References

[1]	N. Ananchuen, M. Plummer, Matchings in 3-vertex-critical graphs: the even case, Networks, 45 (2005), 210–213. http://dx.doi.org/10.1002/net.20065 doi: 10.1002/net.20065
[2]	N. Ananchuen, M. Plummer, Matchings in 3-vertex-critical graphs: the odd case, Discrete Math., 307 (2007), 1651–1658. http://dx.doi.org/10.1016/j.disc.2006.09.015 doi: 10.1016/j.disc.2006.09.015
[3]	J. Bondy, U. Murty, Graph theory with applications, London: Macmillan Press, 1976.
[4]	R. Brigham, P. Chinn, R. Dutton, Vertex domination-critical graphs, Networks, 18 (1988), 173–179. http://dx.doi.org/10.1002/net.3230180304 doi: 10.1002/net.3230180304
[5]	R. Brigham, T. Haynes, M. Henning, D. Rall, Bicritical domination, Discrete Math., 305 (2005), 18–32. http://dx.doi.org/10.1016/j.disc.2005.09.013
[6]	T. Burton, D. Sumner, Domination dot-critical graphs, Discrete Math., 306 (2006), 11–18. http://dx.doi.org/10.1016/j.disc.2005.06.029 doi: 10.1016/j.disc.2005.06.029
[7]	G. Chartrand, P. Zhang, A chessboard problem and irregular domination, Bull. ICA, 98 (2023), 43–59.
[8]	X. Chen, S. Fujita, M. Furuya, M. Sohn, Constructing connected bicritical graphs with edge-connectivity 2, Discrete Appl. Math., 160 (2012), 488–493. http://dx.doi.org/10.1016/j.dam.2011.03.012 doi: 10.1016/j.dam.2011.03.012
[9]	J. Fulman, D. Hanson, G. Macgillivray, Vertex domination-critical graphs, Networks, 25 (1995), 41–43. http://dx.doi.org/10.1002/net.3230250203 doi: 10.1002/net.3230250203
[10]	M. Furuya, Construction of $(\gamma, k)$-critical graphs, Australas. J. Comb., 53 (2012), 53–65.
[11]	M. Furuya, On the diameter of domination bicritical graphs, Australas. J. Comb., 62 (2015), 184–196.
[12]	P. Grobler, A. Roux, Coalescence and criticality of graphs, Discrete Math., 313 (2013), 1087–1097. http://dx.doi.org/10.1016/j.disc.2013.01.027 doi: 10.1016/j.disc.2013.01.027
[13]	B. Hartnell, D. Rall, On dominating the Cartesian product of a graph and $K_2$, Discuss. Math. Graph T., 24 (2004), 389–402. http://dx.doi.org/10.7151/dmgt.1238 doi: 10.7151/dmgt.1238
[14]	T. Haynes, S. Hedetniemi, P. Slater, Fundamentals of domination in graphs, New York: Marcel Dekker, 1998. http://dx.doi.org/10.1201/9781482246582
[15]	T. Haynes, S. Hedetniemi, P. Slater, Domination in graphs: advanced topics, New York: Marcel Dekker, 1998. http://dx.doi.org/10.1201/9781315141428
[16]	A. Kazemi, Every $K_{1, 7}$ and $K_{1, 3}$-free, 3-vertex-critical graph of even order has a perfect matching, J. Discret. Math. Sci. C., 13 (2010), 583–591. http://dx.doi.org/10.1080/09720529.2010.10698316 doi: 10.1080/09720529.2010.10698316
[17]	M. Krzywkowski, D. Mojdeh, Bicritical domination and double coalescence of graphs, Georgian Math. J., 23 (2016), 399–404. http://dx.doi.org/10.1515/gmj-2016-0019 doi: 10.1515/gmj-2016-0019
[18]	C. Mays, P. Zhang, Irregular domination graphs, Contrib. Math., 6 (2022), 5–14. http://dx.doi.org/10.47443/cm.2022.033
[19]	D. Mojdeh, P. Firoozi, Characteristics of $(\gamma, 3)$-critical graphs, Appl. Anal. Discr. Math., 4 (2010), 197–206. http://dx.doi.org/10.2298/AADM100206013M doi: 10.2298/AADM100206013M
[20]	D. Mojdeh, P. Firoozi, R. Hasni, On connected $(\gamma, k)$-critical graphs, Australas. J. Comb., 46 (2010), 25–35.
[21]	J. Phillips, T. Haynes, P. Slater, A generalization of domination critical graphs, Utilitas Mathematica, 58 (2000), 129–144.
[22]	T. Wang, Q. Yu, Factor-critical property in $3$-dominating-critical graphs, Discrete Math., 309 (2009), 1079–1083. http://dx.doi.org/10.1016/j.disc.2007.11.062 doi: 10.1016/j.disc.2007.11.062
[23]	T. Wang, Q. Yu, A conjecture on $k$-factor-critical and $3$-$\gamma$-critical graphs, Sci. China Math., 53 (2010), 1385–1391. http://dx.doi.org/10.1007/s11425-009-0192-6 doi: 10.1007/s11425-009-0192-6
[24]	Y. Wang, F. Wang, W. Zhao, Construction for trees without domination critical vertices, AIMS Mathematics, 6 (2021), 10696–10706. http://dx.doi.org/10.3934/math.2021621 doi: 10.3934/math.2021621
[25]	W. Zhao, R. Lin, J. Cai, On construction for trees making the equality hold in Vizing's conjecture, J. Graph Theor., 101 (2022), 397–427. http://dx.doi.org/10.1002/jgt.22833 doi: 10.1002/jgt.22833

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)