运筹学学报 >
2021 , Vol. 25 >Issue 1: 137 - 140
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.01.014
关于拟k-连通图的一个注释
收稿日期: 2019-05-30
网络出版日期: 2021-03-05
基金资助
国家自然科学基金(11871246);福建省自然科学基金(2016J01666)
A note on quasi k-connected graphs
Received date: 2019-05-30
Online published: 2021-03-05
G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1|≥2,|G2|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t>
林晓霞 . 关于拟k-连通图的一个注释[J]. 运筹学学报, 2021 , 25(1) : 137 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.014
Let G be a k-connected graph, and T be a k-vertex-cut of a k-connected graph G. If G-T can be partitioned into subgraphs G1 and G2 such that |G1| ≥ 2, |G2| ≥ 2, then we call T a nontrivial k-vertex-cut of G. Suppose that G is a (k-1)-connected graph without nontrivial (k-1)-vertex-cut, then we call G a quasi k-connected graph. In this paper, we prove that for any integer k ≥ 5 and t>
Key words: quasi k-connected graph; component
| 1 | Politof T , Satyanarayana A . Minors of quasi 4-connected graphs[J]. Discrete Mathematics, 1994, 126, 245- 256. |
| 2 | Politof T , Satyanarayana A . The structure of quasi 4-connected graphs[J]. Discrete Mathematics, 1996, 161, 217- 228. |
| 3 | Jiang H , Su J . Minimum degree of minimally quasi (k+1)-connected graphs[J]. Journal of Mathematical Study, 2002, 35 (2): 187- 193. |
| 4 | Xu L , Guo X . Removable edges in a 5-connected graph and a construction method of 5-connectedgraphs[J]. Discrete Mathematics, 2008, 308, 1726- 1731. |
| 5 | Su J , Guo X , Xu L . Removable edges in a k-connected graph and a construction method for k-connectedgraphs[J]. Discrete Mathematics, 2009, 309, 3161- 3165. |
| 6 | Ando K , Kawarabayashi K . Some forbidden subgraph conditions for a graph to have a k-contractible edge[J]. Discrete Mathematics, 2003, 267, 3- 11. |
| 7 | Su J , Yuan X . A new degree sun condition for the existence of a contractible edge in a k-connected graph[J]. Journal of Combinatorial Theory (Ser. B), 2006, 96, 276- 295. |
| 8 | Yang Y . A result on quasi k-connected graphs[J]. Applied Mathematics——A Journal of Chinese Universities(Ser. B), 2015, 30 (2): 245- 252. |
/
| 〈 |
|
〉 |