Super Cyclically Edge Connected Half Vertex Transitive Graphs

Haining Jiang, Jixiang Meng, Yingzhi Tian

College of Mathematics and System Sciences, Xinjiang University, Urumqi, China.

DOI: 10.4236/am.2013.42053                

Abstract

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.

Keywords

Cyclic Edge-Connectivity; Cyclically Optimal; Super Cyclically Edge-Connected; Half Vertex Transitive Graph

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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