Journal of Guangxi Normal University(Natural Science Edition) ›› 2022, Vol. 40 ›› Issue (4): 145-153.doi: 10.16088/j.issn.1001-6600.2021090404

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] FU Wen, REN Baoping, LIN Jianzhong, LUAN Ke, WANG Pengcheng, WANG Bing, LI Dayong, ZHOU Qihai. Jiyuan Taihang Mountain Macaque Population and Conservation Status [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(1): 45-52.
[2] ZHENG Jingjin, LIANG Jipeng, ZHANG Kechu, HUANG Aimian, LU Qian, LI Youbang, HUANG Zhonghao. White-headed Langurs Select Foods Based on Woody Plants' Dominances [J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(1): 53-64.
[3] ZHANG Kechu, YUAN Peisong, HUANG Henglian, TANG Xiaoping, ZHOU Qihai, HUANG Zhonghao. Inter-site Variation in Dietary Composition of White-headed Langurs (Trachypithecus leucocephalus) [J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(1): 75-81.
[4] CHEN Yan, WU Wen-kang, LIANG Jun-bin. High Safety Scheme of Key Pre-distribution with a Mobile Sink in Wireless Sensor Network [J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 164-168.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!