magazinelogo

Journal of Applied Mathematics and Computation

ISSN Print: 2576-0645 Downloads: 344276 Total View: 3164537
Frequency: quarterly ISSN Online: 2576-0653 CODEN: JAMCEZ
Email: jamc@hillpublisher.com
ArticleOpen Access http://dx.doi.org/10.26855/jamc.2025.03.007

The Cohesive Degree Condition of Non-separating Subtree Problems in Graph Partition

Kaixin Lin

School of Computing and Information Science, Fuzhou Institute of Technology, Fuzhou 350500, Fujian, China.

*Corresponding author:Kaixin Lin

Published: April 21,2025

Abstract

This paper focuses on a conjecture proposed by Locke in 1998 about the partition of subtrees in graphs, that is, all 2m-cohesive degree condition graphs contain trees with arbitrary m vertices, and the graph remains connected after removing the subtrees. Here, 2m-cohesive means that the sum of the degrees and the distance for any two vertices is greater than or equal to 2m. In this paper, we discuss the cases according to the minimum degree of the graphs, and use the method of induction hypothesis on the number of vertices. In addition, we give the existing condition of the cohesive form of any subtree. Based on the conclusion of Locke’s conjecture, this paper also generalizes to the tree partition problem of k-connected graphs and part of the conclusions of Mader’s conjecture. The results in this paper proved that the conjecture holds for all tree classes except stars and double stars.

Keywords

Locke’s conjecture; cohesive graph; non-separating tree; connected graph

References

[1] Bondy JA, Murty USR. Graph Theory. Springer; 2008.

[2] Thomassen C. Graph decomposition with applications to subdivisions and path systems modulo k. J Graph Theory. 1983;7:261-271. https://doi.org/10.1002/jgt.3190070215

[3] Kriesell M. Induced paths in 5-connected graphs. J Graph Theory. 2001;36:52-58.

https://doi.org/10.1002/1097-0118(200101)36:1<52::AID-JGT5>3.0.CO;2-N

[4] Chen G, Gould RJ, Yu X. Graph Connectivity After Path Removal. Combinatorica. 2003;23:185-203.

https://doi.org/10.1007/s003-0018-z

[5] Mader W. Connectivity keeping paths in k-connected graphs. J Graph Theory. 2010;65:61-69. https://doi.org/10.1002/jgt.20465

[6] Chartrand G, Kaigars A, Lick DR. Critically n-connected graphs. Proc Am Math Soc. 1972;32:63-68.

https://doi.org/10.2307/2038307

[7] Diwan AA, Tholiya NP. Non-separating trees in connected graphs. Discrete Math. 2009;309:5235-5237.

https://doi.org/10.1016/j.disc.2009.03.037

[8] Tian Y, Meng J, Lai H, Xu L. Connectivity keeping stars or double-stars in 2-connected graphs. Discrete Math. 2018;341:1120-1124. https://doi.org/10.1016/j.disc.2017.10.017

[9] Tian Y, Lai H, Xu L, Meng J. Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs. Discrete Math. 2019;342:344-351.
https://doi.org/10.1016/j.disc.2018.10.001

[10] Hong Y, Liu Q, Lu C, Ye Q. Connectivity keeping caterpillars and spiders in 2-connected graphs. Discrete Math. 2021;344:112236. https://doi.org/10.1016/j.disc.2020.112236

[11] Hong Y, Liu Q. Mader’s conjecture for graphs with small connectivity. J Graph Theory. 2022;101:379-388.

https://doi.org/10.1002/jgt.22831

[12] Fujita S, Kawarabayashi K. Connectivity keeping edges in graphs with large minimum degree. J Comb Theory Ser B. 2008;98:805-811. https://doi.org/10.1016/j.jctb.2007.11.001

[13] Mader W. Connectivity keeping trees in k-connected graphs. J Graph Theory. 2012;69:324-329. https://doi.org/10.1002/jgt.20585

[14] Lovasz L. Combinatorial Problems and Exercises. 2nd ed. North Holland; 1993. https://doi.org/10.1016/C2009-0-09109-0

[15] Thomassen C, Toft B. Non-separating induced cycles in graphs. J Comb Theory Ser B. 1981;31:199-224.

https://doi.org/10.1016/S0095-8956(81)80025-1

[16] Locke SC. Problem 10647. Am Math Mon. 1998;105:176. https://doi.org/10.2307/2589657

[17] Locke SC, Tracy P, Voss HJ. Highly cohesive graphs have long nonseparating paths: 10647. Am Math Mon. 2001;108:470-472. https://doi.org/10.2307/2695811

[18] Abreu M, Locke SC. Non-separating n trees up to diameter 4 in a (2n + 2)-cohesive graph. Congr Numerantium. 2002;154:21-30.

[19] Mader W. Existenz gewisser Konfigurationen in n-gesättigten Graphen und in Graphen genügend großer Kantendichte. Math Ann. 1971;194:295-312.
https://doi.org/10.1007/BF01350130

[20] Liu Q, Ying K, Hong Y. Highly connected triples and Mader’s conjecture. J Graph Theory. 2024;107:478-484.

https://doi.org/10.1002/jgt.23144

[21] Hasunuma T, Ono K. Connectivity keeping trees in 2-connected graphs. J Graph Theory. 2020;94:20-29.

https://doi.org/10.1002/jgt.22504

[22] Lu C, Zhang P. Connectivity keeping trees in 2-connected graphs. Discrete Math. 2020;343:111677.

https://doi.org/10.1016/j.disc.2019.111677

How to cite this paper

The Cohesive Degree Condition of Non-separating Subtree Problems in Graph Partition

How to cite this paper: Kaixin Lin. (2025) The Cohesive Degree Condition of Non-separating Subtree Problems in Graph Partition. Journal of Applied Mathematics and Computation9(1), 53-56.

DOI: http://dx.doi.org/10.26855/jamc.2025.03.007