A note on quasi k-connected graphs

Expand
  • 1. Teachers College, Jimei University, Xiamen 361021, Fujian, China

Received date: 2019-05-30

  Online published: 2021-03-05

Abstract

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> $ \frac{k}{2}$, if G is a (K2+tK1)-free k-connected graph for which d (v)+d (w)≥ $\frac{{3k}}{2} $+t for any pair v, w of distinct vertices of G, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least $\frac{{\left| {V\left( G \right)} \right|}}{2} $ edges of G such that the contraction of every member of the results in a quasi k-connected graph.

Cite this article

Xiaoxia LIN . A note on quasi k-connected graphs[J]. Operations Research Transactions, 2021 , 25(1) : 137 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.014

References

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.
Outlines

/