Results on monochromatic vertex disconnection of graphs

Miao Fu; Yuqin Zhang; Miao Fu; Yuqin Zhang

doi:10.3934/math.2023668

AIMS Mathematics

2023, Volume 8, Issue 6: 13219-13240. doi: 10.3934/math.2023668

Previous Article Next Article

Research article

Results on monochromatic vertex disconnection of graphs

Miao Fu ¹,
Yuqin Zhang ^{2
,
,}

1.
Center for Applied Mathematics, Tianjin University, Tianjin 300072, China
2.
School of Mathematics, Tianjin University, Tianjin 300072, China

Received: 14 February 2023 Revised: 17 March 2023 Accepted: 22 March 2023 Published: 03 April 2023
MSC : 05C15, 05C35, 05C40

Let $ G $ be a vertex-colored graph. A vertex cut $ S $ of $ G $ is called a monochromatic vertex cut if the vertices of $ S $ are colored with the same color. A graph $ G $ is monochromatically vertex-disconnected if any two nonadjacent vertices of $ G $ have a monochromatic vertex cut separating them. The monochromatic vertex disconnection number of $ G $, denoted by $ mvd(G) $, is the maximum number of colors that are used to make $ G $ monochromatically vertex-disconnected. In this paper, the connection between the graph parameters are studied: $ mvd(G) $, connectivity and block decomposition. We determine the value of $ mvd(G) $ for some well-known graphs, and then characterize $ G $ when $ n-5\leq mvd(G)\leq n $ and all blocks of $ G $ are minimally 2-connected triangle-free graphs. We obtain the maximum size of a graph $ G $ with $ mvd(G) = k $ for any $ k $. Finally, we study the Erdős-Gallai-type results for $ mvd(G) $, and completely solve them.
- monochromatic vertex cut,
- monochromatic vertex disconnection number,
- connectivity,
- block,
- Erdős-Gallai-type problems
Citation: Miao Fu, Yuqin Zhang. Results on monochromatic vertex disconnection of graphs[J]. AIMS Mathematics, 2023, 8(6): 13219-13240. doi: 10.3934/math.2023668

Related Papers:

Abstract

Let $ G $ be a vertex-colored graph. A vertex cut $ S $ of $ G $ is called a monochromatic vertex cut if the vertices of $ S $ are colored with the same color. A graph $ G $ is monochromatically vertex-disconnected if any two nonadjacent vertices of $ G $ have a monochromatic vertex cut separating them. The monochromatic vertex disconnection number of $ G $, denoted by $ mvd(G) $, is the maximum number of colors that are used to make $ G $ monochromatically vertex-disconnected. In this paper, the connection between the graph parameters are studied: $ mvd(G) $, connectivity and block decomposition. We determine the value of $ mvd(G) $ for some well-known graphs, and then characterize $ G $ when $ n-5\leq mvd(G)\leq n $ and all blocks of $ G $ are minimally 2-connected triangle-free graphs. We obtain the maximum size of a graph $ G $ with $ mvd(G) = k $ for any $ k $. Finally, we study the Erdős-Gallai-type results for $ mvd(G) $, and completely solve them.

References

[1]	P. Allen, J. Böttcher, O. Cooley, R. Mycroft, Tight cycles and regular slices in dense hypergraphs, J. Combin. Theory A, 149 (2017), 30–100. https://doi.org/10.1016/j.jcta.2017.01.003 doi: 10.1016/j.jcta.2017.01.003
[2]	J. A. Bondy, U. S. R. Murty, Graph Theory, Berlin: Springer, 2008.
[3]	Y. Caro, R. Yuster, Colorful monochromatic connectivity, Discrete Math., 311 (2011), 1786–1792. https://doi.org/10.1016/j.disc.2011.04.020 doi: 10.1016/j.disc.2011.04.020
[4]	Q. Q. Cai, X. L. Li, D. Wu, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, J. Comb. Optim., 35 (2018), 1300–1311. https://doi.org/10.1007/s10878-018-0258-x doi: 10.1007/s10878-018-0258-x
[5]	G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem., 133 (2008), 85–98. https://doi.org/10.21136/MB.2008.133947 doi: 10.21136/MB.2008.133947
[6]	G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks, 54 (2009), 75–81. https://doi.org/10.1002/net.20296 doi: 10.1002/net.20296
[7]	A. Dudek, A. M. Frieze, C. E. Tsourakakis, Rainbow connection of random regular graphs, SIAM J. Discrete Math., 29 (2015), 2255–2266. https://doi.org/10.1137/140998433 doi: 10.1137/140998433
[8]	P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Mathematica Academiae Scientiarum Hungarica, 10 (1959), 337–356. https://doi.org/10.1007/bf02024498 doi: 10.1007/bf02024498
[9]	R. J. Faudree, R. H. Schelp, Path ramsey numbers in multicolorings, J. Comb. Theory B, 19 (1975), 150–160. https://doi.org/10.1016/0095-8956(75)90080-5 doi: 10.1016/0095-8956(75)90080-5
[10]	R. Gu, X. L. Li, Z. M. Qin, Y. Zhao, More on the colorful monochromatic connectivity, Bull. Malays. Math. Sci. Soc., 40 (2017), 1769–1779. https://doi.org/10.1007/s40840-015-0274-2 doi: 10.1007/s40840-015-0274-2
[11]	F. Harary, Conditional connectivity, Networks, 13 (1983), 347–357. https://doi.org/10.1002/net.3230130303 doi: 10.1002/net.3230130303
[12]	A. M. Hobbs, A catalog of minimal blocks, Journal Of Research of the Notional Bureau of Standards-B, 77B (1973), 53–60. https://doi.org/10.6028/jres.077b.005 doi: 10.6028/jres.077b.005
[13]	T. P. Kirkman, On the representation of polyhedra, Philos. Trans. Roy. Soc. London Ser. A, 146 (1856), 413–418. https://doi.org/10.1098/rspl.1854.0122 doi: 10.1098/rspl.1854.0122
[14]	Z. P. Lu, Y. B. Ma, Graphs with vertex rainbow connection number two, Sci. China Math., 58 (2015), 1803–1810. https://doi.org/10.1007/s11425-014-4905-0 doi: 10.1007/s11425-014-4905-0
[15]	P. Li, X. L. Li, Monochromatic disconnection: Erdős-Gallai-type problems and product graphs, J. Comb. Optim., 44 (2022), 136–153. https://doi.org/10.1007/s10878-021-00820-3 doi: 10.1007/s10878-021-00820-3
[16]	M. Lewin, On maximal circuits in directed graphs, J. Comb. Theory B, 18 (1975), 175–179. https://doi.org/10.1016/0095-8956(75)90045-3 doi: 10.1016/0095-8956(75)90045-3
[17]	X. L. Li, S. J. Liu, A sharp upper bound for the rainbow 2-connection number of a 2-connected graph, Discrete Math., 313 (2013), 755–759. https://doi.org/10.1016/j.disc.2012.12.014 doi: 10.1016/j.disc.2012.12.014
[18]	X. L. Li, Y. F. Sun, An updated survey on rainbow connections of graphs - a dynamic survey, Theory and Applications of Graphs, 1 (2017), 3. https://doi.org/10.20429/tag.2017.000103 doi: 10.20429/tag.2017.000103
[19]	Y. B. Ma, L. Chen, H. Z. Li, Graphs with small total rainbow connection number, Front. Math. China, 12 (2017), 921–936. https://doi.org/10.1007/s11464-017-0651-2 doi: 10.1007/s11464-017-0651-2
[20]	B. Ning, X. Peng, Extensions of the Erdős-Gallai theorem and Luo's theorem, Comb. Probab. Comput., 29 (2020), 128–136. https://doi.org/10.1017/S0963548319000269 doi: 10.1017/S0963548319000269
[21]	M. D. Plummer, On minimal blocks, Trans. Amer. Math. Soc., 134 (1968), 85–94. https://doi.org/10.1090/S0002-9947-1968-0228369-8 doi: 10.1090/S0002-9947-1968-0228369-8
[22]	Y. Shang, A sharp threshold for rainbow connection in small-world networks, Miskolc Math. Notes, 13 (2012), 493–497. https://doi.org/10.18514/MMN.2012.347 doi: 10.18514/MMN.2012.347
[23]	Y. L. Shang, Concentration of rainbow k-connectivity of a multiplex random graph, Theor. Comput. Sci., 951 (2023), 113771. https://doi.org/10.1016/j.tcs.2023.113771 doi: 10.1016/j.tcs.2023.113771

Reader Comments

Your name:*

Email:*
© 2023 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)