一类特殊坚韧图的性质
Properties of Some Class of Special Tough Graphs
DOI: 10.12677/AAM.2023.121018, PDF,    科研立项经费支持
作者: 马 惠, 杨卫华*：太原理工大学，数学学院，山西 晋中
关键词: 坚韧度；极小t-坚韧图；连通度；最小度；K1；n-free图；Toughness； Minimally t-Tough Graphs； Connectivity； Minimum Degree； K1；n-Free Graphs
摘要: 连通图G的坚韧度定义为。如果G的坚韧度是t，并且删去G的任意一条边后其坚韧度减小，则称G是极小t-坚韧的。Matthews等证明了K1,3-free图的连通度是其坚韧度的2倍。本文证明了坚韧度为t的K1,n-free图的连通度不超过(n-1)t，且极小1-坚韧，K1,4-free图的连通度为2。此外，Kriesell猜想极小1-坚韧图的最小度是2。Katona等推广了上述猜想，极小t-坚韧图的最小度是 。本文证明了极小1/(n-1)-坚韧，K1,n-free图的最小度为1，其中n≥3。
Abstract: The toughness of G is defined as . A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Matthews et al. has proved that the connectivity of K1,3 -free graphs is twice its tough-ness. This paper shows that the connectivity of K1,n -free graphs with toughness t is at most , and the connectivity of minimally 1-tough, K1,4 -free graphs is 2. In addition, Kriesell con-jectured that the minimum degree of minimally 1-graphs is 2. Katona et al. proposed a generalized version of the conjecture that the minimum degree of minimally t-tough graph is . This paper proves that the minimum degree of minimally 1/(n-1)-tough, K1,n -free graphs is 1, where n≥3 .
文章引用：马惠, 杨卫华. 一类特殊坚韧图的性质[J]. 应用数学进展, 2023, 12(1): 147-152. https://doi.org/10.12677/AAM.2023.121018

参考文献

[1] Chvátal, V. (2006) Tough Graphs and Hamiltonian Circuits. Discrete Mathematics, 306, 910-917. [Google Scholar] [CrossRef] 
[2] Bermond, J.C. (1978) Hamiltonian Graphs. In: Beineke, L. and Wilson, R.J., Eds., Seleted Topics in Graph Theorey, Academic Press, London, 127-167.
[3] Bauer, D., Katona, G.Y., Kratsch, D. and Veldman, H.J. (2000) Chordality and 2-Factors in Tough Graphs. Discrete Applied Mathematics, 99, 323-329. [Google Scholar] [CrossRef] 
[4] Kabel, A. and Kaiser, T. (2017) 10-Tough Chordal Graphs Are Hamiltonian. Journal of Combinatorial Theory, Series B, 122, 417-427. [Google Scholar] [CrossRef] 
[5] Kratsh, D., Lehel, J. and Müller, H. (1996) Toughness, Hamiltonic-ity and Split Graphs. Discrete Mathematics, 150, 231-245. [Google Scholar] [CrossRef] 
[6] Shi, L. and Shan, S. (2022) A Note on Hamiltonian Cycles in 4-Tough -Free Graphs. Discrete Mathematics, 345, Article ID: 113081. [Google Scholar] [CrossRef] 
[7] Ota, K. and Sanka, M. (2022) Hamiltonian Cycles in 2-Tough -Free Graphs. Journal of Graph Theory, 101, 769-781. [Google Scholar] [CrossRef] 
[8] Gao, Y. and Shan, S. (2022) Hamiltonian Cycles in 7-Tough -Free Graphs. Discrete Mathematics, 345, Article ID: 113069. [Google Scholar] [CrossRef] 
[9] Lu, H. and Kano, M. (2020) Characterization of 1-Tough Graphs Using Factors. Discrete Mathematics, 343, Article ID: 111901. [Google Scholar] [CrossRef] 
[10] Enomoto, H., Jackson, B., Katerinis, P. and Saito, A. (1985) Toughness and the Existence of k-Factors. Journal of Graph Theory, 9, 87-95. [Google Scholar] [CrossRef] 
[11] Broersma, H., Engbers, E. and Trommel, H. (1999) Various Results on the Toughness of Graphs. Networks, 33, 233-238. [Google Scholar] [CrossRef] 
[12] Katona, G.Y., Soltesz, D. and Varga, K. (2018) Properties of Minimally t-Tough Graphs. Discrete Mathematics, 341, 221-231. [Google Scholar] [CrossRef] 
[13] Mader, W. (1971) Eine Eigenschaft der Atome endlicher Graphen. Archiv der Mathematik, 22, 333-336. [Google Scholar] [CrossRef] 
[14] Kaiser, T. (2003) Problems from the Workshop on Dominating Cycles. http://iti.zcu.cz/history/2003/Hajek/problems/hajek-problems.ps
[15] Katona, G.Y. and Varga, K. (2018) Minimally Toughness in Special Graph Classes. ArXiv: 1802.00055.
[16] Matthews, M.M. and Sumner, D.P. (1984) Hamiltonian Results in -Free Graphs. Journal of Graph Theory, 8, 139-146. [Google Scholar] [CrossRef] 

为你推荐