Share This Article:

Super Cyclically Edge Connected Half Vertex Transitive Graphs

Abstract Full-Text HTML XML Download Download as PDF (Size:170KB) PP. 348-351
DOI: 10.4236/am.2013.42053    2,389 Downloads   3,989 Views   Citations


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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.


[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

comments powered by Disqus

Copyright © 2018 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.