Super Cyclically Edge Connected Half Vertex Transitive Graphs


Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.

Share and Cite:

H. Jiang, J. Meng and Y. Tian, "Super Cyclically Edge Connected Half Vertex Transitive Graphs," Applied Mathematics, Vol. 4 No. 2, 2013, pp. 348-351. doi: 10.4236/am.2013.42053.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] S. Latifi, M. Hegde and M. Naraghi-Pour, “Conditional Connectivity Measures for Large Multiprocessor Systems,” IEEE Transactions on Compututers, Vol. 43, No. 2, 1994, pp. 218-222. doi:10.1109/12.262126
[2] L. Lovász, “On Graphs Not Containing Independent Circuits,” Matematikai Lapok, Vol. 16, No. 3, 1965, pp. 289-299.
[3] B. Bollobas, “Extremal Graph Theory,” Academic Press, London, 1978.
[4] M. D. Plummer, “On the Cyclic Connectivity of Planar Graphs,” Lecture Notes in Mathematics, Vol. 303, No. 1, 1972, pp. 235-242. doi:10.1007/BFb0067376
[5] P. G. Tait, “Remarks on the Colouring of Maps,” Proceedings of the Royal Society of Edinburgh, Vol. 10, No. 4, 1880, pp. 501-503.
[6] E. Macajova and M. Soviera, “Infinitely Many Hypohamiltonian Cubic Graphs of Girth 7,” Graphs and Combinatorics, Vol. 27, No. 2, 2011, pp. 231-241. doi:10.1007/s00373-010-0968-z
[7] F. Kardos and R. Srekovski, “Cyclic Edge-Cuts in Fullerence Graphs,” Journal of Mathematical Chemistry, Vol. 44, No. 1, 2008, pp. 121-132. doi:10.1007/s10910-007-9296-9
[8] C. Q. Zhang, “Integer Flows and Cycle Covers of Graphs,” Marcel Dekker, New York, 1997.
[9] D. A. Holton, D. Lou and M. D. Plummer, “On the 2-Extendability of Planar Graphs,” Discrete Mathematics, Vol. 96, No. 2, 1991, pp. 81-99. doi:10.1016/0012-365X(91)90227-S
[10] D. Lou and D. A. Holton, “Lower Bound of Cyclic Edge Connectivity for n-Extendability of Regular Graphs,” Discrete Mathematics, Vol. 112, No. 1-3, 1993, pp. 139-150. doi:10.1016/0012-365X(93)90229-M
[11] B. Wang and Z. Zhang, “On the Cyclic Edge—Connectivity of Transitive Graphs,” Discrete Mathematics, Vol. 309, No. 13, 2009, pp. 4555-4563. doi:10.1016/j.disc.2009.02.019
[12] M. Y. Xu, J. H. Huang, H. L. Li and S. R. Li , “Introduction to Group Theory,” Academic Publishes, Beijing, 1999.
[13] J. X. Meng, “Optimally Super-Edge-Connected Transitive Graphs,” Discrete Mathematics, Vol. 206, No. 1-3, 2003, pp. 239-248. doi:10.1016/S0012-365X(02)00675-1
[14] J. M. Xu, “On Conditional Edge-Connectivity of Graphs,” Acta Mathematica Applicatae Sinica, Vol. 16, No. 4, 2000, pp. 414-419. doi:10.1007/BF02671131
[15] R. Nedela and M. Soviera, “Atoms of Cyclic Connectivity in Cublic Graphs,” Mathematica Slovaca, Vol. 45, No. 5, 1995, pp. 481-499.
[16] J. M. Xu and Q. Liu, “2-Restricted Edge-Connectivity of Vertex-Transitive Graphs,” Australasian Journal of Combinatorics, Vol. 30, No. 1, 2004, pp. 41-49.
[17] Z. Zhang and B. Wang, “Super Cyclically Edge-Connected Transitive Graphs,” Joumal of Combinatorial Optimization, Vol. 22, No. 4, 2011, pp. 549-562. doi:10.1007/s10878-010-9304-z
[18] J. X. Zhou and Y. Q. Feng, “Super-Cyclically Edge-Connected Regular Graphs,” Joumal of Combinatorial Optimization, 2012.
[19] Y. Z. Tian and J. X. Meng, “ -Optimally Half Vertex Transitive Graphs with Regularity k,” Information Processing Letters, Vol. 109, No. 13, 2009, pp. 683-686. doi:10.1016/j.ipl.2009.03.001
[20] R. Tindell, “Connectivity of Cayley Graphs,” In: D. Z. Du and D. F. Hsu, Eds., Combinatorial Network Theory, Kluwer, Dordrecht, 1996, pp. 41-64. doi:10.1007/978-1-4757-2491-2_2

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.