广西师范大学学报（自然科学版） ›› 2022, Vol. 40 ›› Issue (4): 145-153.doi: 10.16088/j.issn.1001-6600.2021090404

• 研究论文 • 上一篇    下一篇

C3-和C4-临界连通图的结构

覃城阜*, 莫芬梅   

  1. 南宁师范大学数学与统计学院,广西南宁 530001
  • 发布日期:2022-08-05
  • 通讯作者: 覃城阜(1979—),男, 广西环江人, 南宁师范大学副教授, 博士。 E-mail: qtclf@163.com
  • 基金资助:
    国家自然科学基金 (11961051);广西自然科学基金(2018GXNSFAA050117)

Structure ofC3-and C4-Critical Graphs

QIN Chengfu*, MO Fenmei   

  1. College of Mathematics and Statistics, Nanning Normal University, Nanning Guangxi 530001, China
  • Published:2022-08-05

PDF (PC)

467

摘要： 设G是连通图,如果G中每一个阶至多为m的完全子图都包含在一个最小点割内,则称G是Cm-临界图。 Mader证明C3-临界图是6连通图的,Pastor 证明C3-临界极小6-连通图G中由6度点导出的子图G6的每一个分支都有一个圈。 本文运用断片方法证明C3-临界极小6-连通图中每一个点与至少2个6度点相邻,由此可以推出Pastor的结论。进一步,本文证明了C4-临界连通图是7-连通的。

关键词: :Cm-临界, 局部结构, 连通度, 断片

Abstract: A connected graph is said to be Cm-critical if every complete subgraph with order no more than m of G is contained in a smallest separating set. Mader shows that C3-critical graph is 6-connected. Pastor shows that every component of G6,induced by the set of vertices of degree 6 of a minimally C3-critical graph, has a cycle. By using some insight on properties of fragment, it is shown that every vertex of minimally C3-critical graph adjacent to at least two vertices of degree 6, which implies the result of Pastor. Further, it is shown that everyC4-critical connected graph is 7-connected.

Key words: Cm-critical, local structure, connectivity, fragment

中图分类号: 

  • O157.5
[1] MADER W. Generalizations of critical connectivity of graphs[J]. Discrete Mathematics, 1988, 72(1/2/3): 267-283.
[2]CHARTRAND G, KAUGARS A, LICK D R. Critically N-connected graphs[J]. Proceedings of American Mathematical Society, 1971,32(1):63-68.
[3]HAMIDOUNE Y O. On critically h-connected simple graphs[J]. Discrete Mathematic, 1980, 32(3): 257-262.
[4]钟玲平,崔庆. 临界k-连通图中的点度数[J]. 应用数学学报, 2012, 35(5):928-934.
[5]MARTINOV N. Uncontractable 4-connected graphs[J]. Journal of Graph Theory, 1982, 6(3): 343-344.
[6]苏健基. 收缩临界5-连通图中的5度点[J]. 广西师范大学学报(自然科学版), 1997, 15(3):12-16.
[7]赵巧凤, 覃城阜, 袁旭东, 等. 收缩临界6连通图中的6度顶点[J]. 广西师范大学学报(自然科学版), 2005,23(2): 38-43.
[8]OBRAZTSOVA S A.Local structure of 5-and 6-connected graphs[J]. Journal of Mathematical Sciences, 2011, 179(5): 621-625.
[9]ANDO K, QIN C F. On the structural properties of minimally contraction-critically 5-connected graphs[J]. Discrete Mathematics, 2010, 311(13): 1084-1097.
[10]LI T T, SU J J. The new lower bound of the number of vertices of degree 5 in contraction critical 5-connected graphs[J]. Graphs and Combinatorics, 2010, 26(3): 395-406.
[11]ANDO K, FUJITA S, KAWARABAYASHI K I. Minimally contraction-critically 6-connected graphs[J]. Discrete Mathematics, 2012, 312(3): 671-679.
[12]QIN C F, GUO X F, ANDO K. The removalbe edges and the contractible subgraph of 5-connected graphs[J]. Graphs and Combinatorics, 2015, 31(1): 243-254.
[13]齐恩凤. 收缩临界7-连通图中的点(英文)[J]. 数学进展, 2013, 42(2):165-167.
[14]QIN C F, HE W H, ANDO K. A constructive characterization of contraction critical 8-connected graphs with minimum degree 9[J]. Discrete Mathematics, 2019, 342(11): 3047-3056.
[15]PASTOR A V. On vertices of degree 6 of minimal and contraction critical 6-connected graph[J]. Journal of Mathematical Sciences, 2021, 255(1): 88-102.
[16]卢建立, 张志芳. 收缩临界6-连通图中的6度点[J]. 数学的实践与认识, 2011, 41(13): 169-173.
[17]PASTOR A V. On the structure of C3-critical minimal 6-connected graphs[J]. Journal of Mathematical Sciences, 2016,212(6): 698-707.
[18]SCHMIDT J M. Tight bounds for the vertices of degree k in minimally k-connected graphs[J]. Journal of Graph Theory, 2018, 88(1): 146-153.
[1] 周志东, 翟莹, 罗正炎. 一个6 阶图H与路Pn,圈Cn的联图的交叉数[J]. 广西师范大学学报（自然科学版）, 2021, 39(6): 112-118.
[2] 翁小雄, 谢志鹏. 基于多层复杂网络的高速公路节点重要性研究[J]. 广西师范大学学报（自然科学版）, 2021, 39(5): 78-88.
[3] 赵红涛, 刘志伟. λ重完全二部3-一致超图λK(3)n,n分解为超图双三角锥[J]. 广西师范大学学报（自然科学版）, 2021, 39(4): 93-98.
[4] 李广, 徐保根, 张君霞. 两类图的Fractional控制数[J]. 广西师范大学学报（自然科学版）, 2021, 39(2): 112-118.
[5] 化小会, 陈利. 陪集图的同构与自同构[J]. 广西师范大学学报（自然科学版）, 2015, 33(4): 68-72.
[6] 唐高华, 熊腾飞, 张培洋, 黄红娣. 整循环图的一些新性质[J]. 广西师范大学学报（自然科学版）, 2012, 30(3): 7-15.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发