同阶双轨道连通图的超圈边连通性

doi:10.3969/j.issn.1007-2861.2016.05.004

上海大学学报(自然科学版) ›› 2017, Vol. 23 ›› Issue (2): 252-256.doi: 10.3969/j.issn.1007-2861.2016.05.004

同阶双轨道连通图的超圈边连通性

姜海宁

厦门大学数学科学学院, 福建厦门 361005

收稿日期:2016-03-23 出版日期:2017-04-30 发布日期:2017-04-30
通讯作者: 姜海宁(1983—), 男, 博士研究生, 研究方向为图论. E-mail: hnjiangsd@163.com
作者简介:姜海宁(1983—), 男, 博士研究生, 研究方向为图论. E-mail: hnjiangsd@163.com
基金资助:
国家自然科学基金资助项目(11471273)

Super cyclically edge connected graphs with two orbits of the same size

JIANG Haining

School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, China

Received:2016-03-23 Online:2017-04-30 Published:2017-04-30

摘要/Abstract

摘要：

对于图G, 如果G−F 是不连通的且至少有两个分支含有圈, 则称F 为图G的圈边割. 如果图G 有圈边割, 则称其为圈可分的. 最小圈边割的基数叫作圈边连通度. 如果去除任何一个最小圈边割, 总存在一分支为最小圈, 则图G 为超圈边连通的. 设G = (G₁,G₂, (V₁, V₂))为双轨道图, 最小度δ(G) ≥4, 围长g(G) ≥6 且|V₁| = |V₂|. 假设G_i 是k_i-正则的, k₁ ≤ k₂且G₁ 包含一个长度为g 的圈, 则G 是超圈边连通的.

关键词: 超圈边连通性, 轨道, 圈边连通度, 圈边割

Abstract:

For a graph G, an edge set F is a cyclic edge-cut if (G−F) is disconnected and at least two of its components contain cycles. If G has a cyclic edge-cut, it is said to be cyclically separable. The cyclic edge-connectivity is cardinality of a minimum cyclic edgecut of G. A graph is super cyclically edge-connected if removal of any minimum cyclic edge-cut makes a component a shortest cycle. Let G = (G₁,G₂, (V₁, V₂)) be a doubleorbit graph with minimum degree δ(G) ≥ 4, girth g ≥6 and |V₁| = |V₂|. Suppose G_i is k_i-regular, k₁ ≤ k₂ and G₁ contains a cycle of length g, then G is super cyclically edge connected.

Key words: cyclic edge-connectivity , orbit, super cyclically edge-connected , cyclic edge-cut

姜海宁. 同阶双轨道连通图的超圈边连通性[J]. 上海大学学报(自然科学版), 2017, 23(2): 252-256.

JIANG Haining. Super cyclically edge connected graphs with two orbits of the same size[J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(2): 252-256.

参考文献

[1] Latifi S, Hegde M, Naraghi-Pour M. Conditional connectivity measures for large multiprocessor systems [J]. IEEE Transactions on Computers, 1994, 43(2): 218-222.
[2] Ji S J, Ma H P, Ma G. The matching energy of graphs with given edge connectivity [J]. Journal of Inequalities and Applications, 2015, 30(1): 60-69.
[3] Sun Y F. Generalized 3-edge-connectivity of Cartesian product graphs [J]. Czechoslovak Mathematical Journal, 2015, 65(1): 107-117.
[4] Chekuri C, Rukkanchanunt T, Xu C. On element-connectivity preserving graph simplification[C]// Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2015: 313-324.
[5] Ning W T. The super connectivity of exchanged crossed cube [J]. Information Processing Letter, 2016, 116(1): 80-84.
[6] Lovász L. On graphs not containing independent circuits [M]. Hungarian: Mat Lapole, 1965: 289-299.
[7] Bollobàs B. Extremal graph theory [M]. London: Academic Press, 1978: 68-76.
[8] Plummer M D. On the cyclic connectivity of planar graphs [J]. Lecture Notes in Mathematics, 1972, 303(6): 235-242.

[9] Tait P G. Remarks on the colouring of maps [J]. Proceedings of the Royal Society of Edinburgh, 1880, 10(1): 501-503.
[10] Robertson N. Minimal cyclic-4-connected graphs [J]. Transactions of the American Mathematical Society, 1984, 284(8): 665-684.
[11] Mácjoá E, Soviera M. Infinitely many hypohamiltonian cubic graphs of girth 7 [J]. Graphs and Combinatorics, 2011, 27(2): 231-241.
[12] Kardos F, Skreovski R. Cyclic edge-cuts in fullerene graphs [J]. Journal of Mathematical Chemistry, 2008, 44(1): 121-132.
[13] Zhang C Q. Integer flows and cycle covers of graphs [M]. New York: Marcel Dekker, 1997: 37-45.
[14] Holton D A, Lou D J, Plummer M D. On the 2-extendability of planar graphs [J]. Discret Mathematics, 1991, 96(2): 81-99.
[15] Lou D J, Holton D A. Lower bound of cyclic edge connectivity for n-extendability of regular graphs [J]. Discrete Mathematics, 1993, 112(2): 139-150.
[16] Wang B, Zhang Z. On the cyclic edge-connectivity of transitive graphs [J]. Discrete Mathematics, 2009, 309(6): 4555-4563.
[17] Zhang Z, Wang B. Super cyclically edge-connected transitive graphs [J]. Journal of Combinatorial Optimization, 2011, 22(4): 549-562.
[18] Meng J X. Optimally super-edge-connected transitive graphs [J]. Discrete Mathematics, 2003, 260(1): 239-248.
[19] Xu J M. On conditional edge-connectivity of graphs [J]. Acta Mathematicae Applicatae Sinica, 2002, 16(4): 414-419.
[20] Nedela R, Skoviera M. Atoms of cyclic connectivity in cublic graphs [J]. Mathematica Slovaca, 1995, 45(5): 481-499.
[21] Xu J M, Liu Q. 2-restricted edge-connectivity of vertex-transitive graphs [J]. Australas J Combin, 2004, 30(5): 41-49.
[22] Zhou J X. Atoms of cyclic edge connectivity in regular graphs [J]. Journal of Combinatorial Optimization, 2016, 31(1): 382-395.
[23] Lin H Q, Yang W H, Meng J X. On cyclic edge connectivity of graphs with two orbits of same size [J]. Journal of Mathematical Study, 2010, 43(3): 1-9.
[24] Tindell R. Connectivity of Cayley graphs [M]. Boston: Springer-Verlag, 1996: 41-64.

同阶双轨道连通图的超圈边连通性

Super cyclically edge connected graphs with two orbits of the same size

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	解钧捷, 郑国莘. 轨道交通 LTE-M 通信系统可靠性分析[J]. 上海大学学报(自然科学版), 2019, 25(6): 859-869.
[2]	梁成功, 张云波. 自旋轨道耦合二维费米气体的热力学性质[J]. 上海大学学报(自然科学版), 2019, 25(6): 914-923.
[3]	张睿, 郑国莘, 解钧捷. LTE-M,用于轨道交通,CBTC,的时延分析[J]. 上海大学学报(自然科学版), 2019, 25(2): 180-188.
[4]	项青, 尹征南, 秦昊. 基于零阶算法的轨道吊结构优化设计[J]. 上海大学学报(自然科学版), 2015, 21(6): 742-748.