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

doi:10.3969/j.issn.1007-2861.2016.05.004

Abstract

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

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments