AM  Vol.4 No.2 , February 2013
Super Cyclically Edge Connected Half Vertex Transitive Graphs
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.


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.
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

 
 
Top