The structure of minimally 2-subconnected graphs

Dingjun Lou; Zongrong Qin; Dingjun Lou; Zongrong Qin

doi:10.3934/math.2022550

AIMS Mathematics

2022, Volume 7, Issue 6: 9871-9883. doi: 10.3934/math.2022550

Previous Article Next Article

Research article

The structure of minimally 2-subconnected graphs

Dingjun Lou ¹,
Zongrong Qin ^{2
,
,}

1.
Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China
2.
Department of Software Engineering, Guangzhou Maritime University, Guangzhou 510725, China

Received: 09 January 2022 Revised: 04 March 2022 Accepted: 11 March 2022 Published: 18 March 2022
MSC : 05C40, 05C85

A graph $ G $ with at least $ 2k $ vertices is called $ k $-subconnected if, for any $ 2k $ vertices in $ G $, there are $ k $ independent paths $ P_{1}, P_{2}, \cdots, P_{k} $ joining the $ 2k $ vertices in pairs. A graph $ G $ is minimally 2-subconnected if $ G $ is $ 2 $-subconnected and $ G-e $ is not $ 2 $-subconnected for any edge e in G. The concept of $ k $-subconnected graphs is introduced in the research of matching theory, and this concept has been found to be related with connectivity of graphs. It is of theorectical interests to characterize the structure of minimally $ k $-subconnected graphs. In this paper, we characterize the structure of minimally $ 2 $-subconnected graphs.
- $ k $-subconnected graph,
- structure of minimally $ 2 $-subconnected graphs,
- independent paths,
- number of deleted edges
Citation: Dingjun Lou, Zongrong Qin. The structure of minimally 2-subconnected graphs[J]. AIMS Mathematics, 2022, 7(6): 9871-9883. doi: 10.3934/math.2022550

Related Papers:

Abstract

A graph $ G $ with at least $ 2k $ vertices is called $ k $-subconnected if, for any $ 2k $ vertices in $ G $, there are $ k $ independent paths $ P_{1}, P_{2}, \cdots, P_{k} $ joining the $ 2k $ vertices in pairs. A graph $ G $ is minimally 2-subconnected if $ G $ is $ 2 $-subconnected and $ G-e $ is not $ 2 $-subconnected for any edge e in G. The concept of $ k $-subconnected graphs is introduced in the research of matching theory, and this concept has been found to be related with connectivity of graphs. It is of theorectical interests to characterize the structure of minimally $ k $-subconnected graphs. In this paper, we characterize the structure of minimally $ 2 $-subconnected graphs.

References

[1]	R. Diestel, Graph theory, New York: Springer-Verlag Inc., 2000. https://doi.org/10.2307/3620535
[2]	R. W. Hung, Optimal vertex ranking of block graphs, Inform. Comput., 206 (2000), 1288–1302. https://doi.org/10.1016/j.ic.2008.08.001 doi: 10.1016/j.ic.2008.08.001
[3]	M. D. Plummer, On $n$-extendable graphs, Discrete Math., 31 (1980), 201–210. https://doi.org/10.1016/0012-365X(80)90037-0 doi: 10.1016/0012-365X(80)90037-0
[4]	Q. Yu, Factors and factor extensions, Simon Fraser University, 1991.
[5]	O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph T., 16 (1996), 41–51. https://doi.org/10.7151/dmgt.1022 doi: 10.7151/dmgt.1022
[6]	R. E. L. Aldred, D. A. Holton, D. Lou, N. Zhong, Characterizing 2k-critical graphs and n-extendable graphs, Discrete Math., 287 (2004), 135–139. https://doi.org/10.1016/j.disc.2004.06.013 doi: 10.1016/j.disc.2004.06.013
[7]	Z. R. Qin, D. J. Lou, H. G. Zhu, J. Liang, Characterization of k-subconnected graphs, Appl. Math. Comput., 364 (2020), 124620. https://doi.org/10.1016/j.amc.2019.124620 doi: 10.1016/j.amc.2019.124620
[8]	O. R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congr. Numerantium, 116 (1996), 231–252.
[9]	B. Peroche, On several sorts of connectivity, Discrete Math., 46 (1983), 267–277. https://doi.org/10.1016/0012-365x(83)90121-8 doi: 10.1016/0012-365x(83)90121-8
[10]	Z. Dvořák, J. Kára, D. Král, O. Pangrác, An algorithm for cyclic edge connectivity of cubic graphs, SWAT, 3111 (2004), 236–247. https://doi.org/10.1007/978-3-540-27810-8_21 doi: 10.1007/978-3-540-27810-8_21
[11]	D. J. Lou, W. Wang, An efficient algorithm for cyclic edge connectivity of regular graphs, Ars Combinatoria, 77 (2005), 311–318.
[12]	D. J. Lou, A square time algorithm for cyclic edge connectivity of planar graphs, Ars Combinatoria, 133 (2017), 69–92.
[13]	C. Thomassen, 2-linked graphs, Eur. J. Combin., 1 (1980), 371–378. https://doi.org/10.1016/S0195-6698(80)80039-4 doi: 10.1016/S0195-6698(80)80039-4
[14]	B. Bollobás, A. Thomason, Highly linked graphs, Combinatorica, 16 (1996), 313–320. https://doi.org/10.1007/BF01261316 doi: 10.1007/BF01261316
[15]	K. Kawarabayashi, A. Kostochka, G. Yu, On sufficient degree conditions for a graph to be k-linked, Comb. Probab. Comput., 15 (2006), 685–694. https://doi.org/10.1017/s0963548305007479 doi: 10.1017/s0963548305007479
[16]	Z. R. Qin, D. J. Lou, The k-subconnectedness of planar graphs, AIMS Math., 6 (2021), 5762–5771. https://doi.org/10.3934/math.2021340 doi: 10.3934/math.2021340
[17]	Z. R. Qin, D. J. Lou, The sufficient conditions for k-subconnected graphs, 2021, Submitted.
[18]	J. A. Bondy, U. S. R. Murty, Graph theory with applications, London: MacMillan Press, 1976. https://doi.org/10.1057/jors.1977.45

Reader Comments

Your name:*

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