关于拟k-连通图的一个注释

展开
  • 1. 集美大学师范学院, 福建厦门 361021
林晓霞 E-mail: lxx@jmu.edu.cn

收稿日期: 2019-05-30

  网络出版日期: 2021-03-05

基金资助

国家自然科学基金(11871246);福建省自然科学基金(2016J01666)

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

摘要

G是一个k-连通图,TG的一个k-点割,若G-T可被划分成两个子图G1G2,且|G1|≥2,|G2|≥2,则称TG的一个非平凡点割。假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任意两个不同点对vw,有dv)+dw)≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。

本文引用格式

林晓霞 . 关于拟k-连通图的一个注释[J]. 运筹学学报, 2021 , 25(1) : 137 -140 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.014

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.

参考文献

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.
文章导航

/