几类极小t-坚韧图的构造
The Construction of Some Classes of Minimally t-Tough Graphs
摘要: 若图G的坚韧度为t，且删除G中任意一条边后坚韧度减小，则称图G是极小t-坚韧的。构造极小t-坚韧图并研究其结构特性在理论和应用上都具有重要意义。证明了几类笛卡尔积图和线图的极小t-坚韧性，并构造出一类k-正则的极小k/2-坚韧图。
Abstract: 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. Constructing a minimally t-tough graph and studying its structural characteristics are of great significance in theory and applications. This paper proves that several kinds of Cartesian product graphs and line graphs are minimally t-tough and also construct a class of k-regular, and minimally k/2-tough graphs.
文章引用：同会利, 魏宗田. 几类极小t-坚韧图的构造[J]. 运筹与模糊学, 2020, 10(3): 167-171. https://doi.org/10.12677/ORF.2020.103017

参考文献

[1] Chvátal, V. (1973) Tough Graphs and Hamiltonian Circuits. Discrete Mathematics, 5, 215-228. [Google Scholar] [CrossRef] 
[2] Bauer, D., Broersma, H. and Schmeichel, E. (2006) Toughness in Graphs—A Survey. Graphs and Combinatorics, 22, 1-35. [Google Scholar] [CrossRef] 
[3] Broersma, H., Eng-bers, E. and Trommel, H. (1999) Various Results on the Toughness of Graphs. Networks: An International Journal, 33, 233-238. [Google Scholar] [CrossRef] 
[4] Katona, G.Y., Soltész, D. and Varga, K. (2018) Properties of Minimally t-Tough Graphs. Discrete Mathematics, 341, 221-231. [Google Scholar] [CrossRef] 
[5] Katona, G.Y. and Varga, K. (2018) Minimally Toughness in Special Graph Classes. arXiv:1802.00055.
[6] Katona, G.Y., Kovács, I. and Varga, K. (2017) The Complexity of Recognizing Minimally Tough Graphs. arXiv:1705.10570.
[7] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan London and Elsevier, New York. [Google Scholar] [CrossRef] 
[8] Chvatal, V. (2006) Tough Graphs and Hamiltonian Circuits. Discrete Mathe-matics, 306, 910-917. [Google Scholar] [CrossRef] 
[9] Gunther, G. and Hartnell, B.L. (1991) On m-Connected and k-Neighbour-Connected Graphs. Graph Theory, Combinatorics, and Applications, 2, 585-596.

为你推荐