Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2018, Vol. 45 Issue (4): 391-393    DOI: 10.3785/j.issn.1008-9497.2018.04.001
数学与计算机科学     
超连通图的充分条件
郭利涛
厦门理工学院 应用数学学院, 福建 厦门 361024
Sufficient conditions for graphs to be super connected
GUO Litao
School of Applied Mathematics, Xiamen University of Technology, Xiamen 361024, Fujian Province, China
 全文: PDF(925 KB)   HTML  
摘要： 设G是一个连通图.图的连通度κ（G）存在一个最小正整数k，使得F⊂V，|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点，则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R（G）=1/（d（v））.得到：设n阶连通图G，最小度为δ，若R（G）<1+2/（δ+1）+（n-2δ-1）/（（n-1）（n-3）），则G是超-κ的.
关键词： 连通度;  逆度;  超连通    
Abstract: Let G be a connected graph. The connectivity κ(G) of a connected graph G is the least positive integer k such that there is F⊂V,|F|=k, and G-F is disconnected or is a trivial graph. If every minimum vertex cut isolates a vertex of G, a graph G is super connected or super-κ. Define the inverse degree of a graph G with no isolated vertices as R(G)=1/(d(v)). In this paper, we show that let G be a connected graph with order n and minimum degree δ, if R(G)<1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)), then G is super-κ.
Key words: connectivity    inverse degree    super connected
收稿日期: 2017-07-31 出版日期: 2018-07-12
CLC:  O157.5  
基金资助: Supported by NSFC(11301440).
作者简介: 郭利涛(1982-),ORCID:http://orcid.org/0000-0003-1410-8509,male,doctor,associate professor,the field of interest is graph theory,E-mail:ltguo2012@126.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
郭利涛

引用本文:

郭利涛. 超连通图的充分条件[J]. 浙江大学学报（理学版）, 2018, 45(4): 391-393.

GUO Litao. Sufficient conditions for graphs to be super connected. Journal of Zhejiang University (Science Edition), 2018, 45(4): 391-393.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2018.04.001    或    https://www.zjujournals.com/sci/CN/Y2018/V45/I4/391

[1] BONDY J,MURTY U.Graph Theory and Its Application[M]. New York:Academic Press, 1976.
[2] KELMANS A. Asymptotic formulas for the probability of k-connectedness of random graphs[J].Theory of Probability and Its Applications,1972,17(2):253-265.
[3] LESNIAK L. Results on the edge-connectivity of graphs[J].Discrete Mathematics, 1974,8(4):351-354.
[4] FIOL M. On super-edge-connected digraphs and bipartite digraphs[J].Journal of Graph Theory, 1992,16(6):545-555.
[5] TIAN Y Z, GUO L T, MENG J X, et al. Inverse degree and super edge-connectivity[J].International Journal of Computer Mathematics, 2012,89(6):752-759.
[6] FAJTLOWICZ S. On conjectures of graffiti Ⅱ[J].Congr Numer, 1987,60:189-197.
[7] DANKELMANNP, SWART H, BERG P V D. Diameter and inverse degree[J].Discrete Mathematics,2008,308(5):670-673.
[8] DANKELMANNP, HELLWIG A, VOLKMANN L. Inverse degree and edge-connectivity[J].Discrete Mathematics, 2009,309(9):2943-2947.
[9] ERDÖS P, PACH J, SPENCER J. On the mean distance between points of a graph[C]//Proceedings of the 250th Anniversary Conference on Graph Theory,Congressus Numerantium 64. Winnipeg:Utilitas Mathematica Publishing Inc,1988:121-124.
[1] 周后卿. 几类整循环图的秩的界[J]. 浙江大学学报（理学版）, 2020, 47(3): 301-305.
[2] 包丽娅, 陈祥恩, 王治文. 完全二部图K 10, n (215 ≤ n ≤ 466)的点可区别E-全染色[J]. 浙江大学学报（理学版）, 2020, 47(1): 60-66.
[3] 唐保祥, 任韩. 图的1-因子数目的递推求法[J]. 浙江大学学报（理学版）, 2019, 46(6): 670-675.
[4] 贾会才. k路覆盖图的新充分条件[J]. 浙江大学学报（理学版）, 2019, 46(6): 666-669.
[5] 柳顺义, 覃忠美. 图的Aα特征多项式系数的一个注记[J]. 浙江大学学报（理学版）, 2019, 46(4): 399-404.
[6] 寇艳芳, 陈祥恩, 王治文. K1,5,p和K1,6,p的点可区别的IE-全染色及一般全染色[J]. 浙江大学学报（理学版）, 2018, 45(5): 533-539.
[7] 周后卿. 卡氏积图的Laplacian谱半径的上界[J]. 浙江大学学报（理学版）, 2018, 45(1): 10-13,17.
[8] 王国兴. Cartesian积与邻点可区别着色之间的关系[J]. 浙江大学学报（理学版）, 2017, 44(5): 520-525.
[9] 唐保祥, 任韩. 2类特殊图中的完美匹配数[J]. 浙江大学学报（理学版）, 2017, 44(3): 266-269.
[10] 温艳清, 刘宝亮, 安明强. 若干运算图的倍乘赋权Harary指标[J]. 浙江大学学报（理学版）, 2017, 44(3): 253-260,280.
[11] 杜娟, 吕大梅, 张科. Cartesian积的局部边-路替换图的L(2,1)-标号[J]. 浙江大学学报（理学版）, 2016, 43(6): 679-681.
[12] 吕大梅, 林文松. 关于边-多重路替换图的1,2,3-猜想和1,2-猜想[J]. 浙江大学学报（理学版）, 2016, 43(6): 668-671.
[13] 刘剑萍, 吴先章, 陈锦松. 树状六角系统的增强型萨格勒布指数[J]. 浙江大学学报（理学版）, 2016, 43(6): 664-667.
[14] 周后卿. 循环图的预解Estrada指标[J]. 浙江大学学报（理学版）, 2016, 43(5): 517-520.
[15] 曲慧, 刘伟俊. 几个图运算下的图的惯性指数的界[J]. 浙江大学学报（理学版）, 2016, 43(2): 134-137.