|
|
|
| Neighbor Connectivity of Two Kinds of Cayley Graphs |
| Yi-jie SHANG, Rong-xia HAO, Mei-mei GU |
| Mathematics, Beijing Jiaotong University, Beijing 100044, China |
|
|
|
|
Abstract In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs:alternating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Γn. Those are κNB(ANn)=n-1, λNB(ANn)=n-2 and κNB(Sn)=λNB(Γn)=n-1.
|
|
Received: 27 September 2013
|
|
|
| Fund:Supported by the National Natural Science Foundation of China (No. 11371052, 11731002, 11571035). |
| About author:: 05C40;05C90 |
|
|
|
| [1] |
Akers, S.B., Harel, D., Krishnamurthy, B. The star graph:an attractive alternative to the n-cube. Proceedings of the International Conference in Parallel Processing, 393-400, 1987
|
| [2] |
Bondy, J.A., Murty, U.S.R. Graph Theory with Applications. North-Holland, New York, 1976
|
| [3] |
Cheng, E., Lipták, L. Linearly many faults in Cayley graphs generated by transposition trees. Information Sciences, 177:4877-4882(2007)
|
| [4] |
Cheng, E., Lipták, L., Qiu, K., Shen, Z. Cyclic vertex-connectivity of Cayley graphs generated by transposition trees. Graphs and Combinatiorics, 29:835-841(2012)
|
| [5] |
Cheng, E., Lipták, L. Diagnosability of Cayley graphs generated by transposition trees with missing edges. Information Sciences, 238:250-252(2013)
|
| [6] |
Cheng, E., Lipták, L., Shawash, N. Orienting Cayley graphs generated by transposition trees. Computers and Mathematics with Applications, 55:2662-2672(2008)
|
| [7] |
Cheng, E., Lipman, M., Lipták. Strong structural properties of uni-directional star graphs. Discrete Applied Mathematics, 156:2939-2949(2008)
|
| [8] |
Cozzens, M.B., Wu, S.Y. Extreme values of the edge-neighbor-connectivity. Ars Combinatoria, 39:199-210(1995)
|
| [9] |
Doty, L.L. A new bound for neighbor-connectivity of abelian Cayley graphs. Discrete Mathematics, 306:1301-1316(2006)
|
| [10] |
Feng, Y.Q. Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets. Journal of Combinatorial Theory, Series B, 96:67-72(2006)
|
| [11] |
Gunther, G. Neighbor-connectivity in regular graphs. Discrete Applied Mathematics, 11:233-243(1985)
|
| [12] |
Hao, R.X., Zhou, J.X. Characterize a kind of fault tolerance of alternating group network. Acta Mathematica Sinica, Chinese Series, 55(6):1055-1066(2012)
|
| [13] |
Hao, R.X., Feng, Y.Q., Zhou, J.X. Conditional diagnosability of alternating group graphs. IEEE Transactions On Computers, 62(4):827-831(2013)
|
| [14] |
Shang, Y.J., Hao, R.X. Edge neighbor connectivity of Cartesian product graphs. American Journal of Applied Mathematics and Mathematical Sciences, 2(1):27-29(2013)
|
| [15] |
Wan, M., Zhang, Z. A kind of conditional vertex connectivity of star graphs. Applied Mathematics Letters, 22(2):264-267(2009)
|
| [16] |
Xu, J.M. Combination of Network Theory. Science Press, Beijing, 2007
|
| [17] |
Xu, M.Y. Automorphism groups and isomorphisms of Cayley digraphs. Discrete Mathematics, 182:309-319(1998)
|
| [18] |
Yang, W.H., Li, H.Z., Meng, J.X. Conditional connectivity of Cayley graphs generated by transposition trees. Information Processing Letters, 1027-1030, 2010
|
| [19] |
Zhao, X.B., Zhang, Z., Ren, Q. Edge neighbor connectivity of Cartesian product graph G×K2. Applied Mathematics and Computation, 217:5508-5511(2011)
|
| [20] |
Zhou, S.M. The Study of fault tolerance on alternating group networks. The 2nd International Conference on BioMedical Engineering and Informatics, 2040-2044, 2009
|
| [21] |
Zhou, S., Xiao, W. Conditional diagnosability of alternating group networks. Information Processing Letters, 110:403-409(2010)
|
| [22] |
Zheng, S.X. Fault tolerance analysis of alternating group networks. Fujian Normal University, Fuzhou, 2008
|
| [1] |
Yan Quan FENG, Jin Ho Kwak, Ming Yao XU. On the Stabilizer of the Automorphism Group of a 4-valent Vertex-transitive Graph with Odd-prime-power Order[J]. Acta Mathematicae Applicatae Sinica, English Serie, 2003, 19(1): 83-86. |
| [2] |
Yan Quan FENG, Jin Ho Kwak, Ming Yao XU. On the Stabilizer of the Automorphism Group of a 4-valent Vertex-transitive Graph with Odd-prime-power Order[J]. Acta Mathematicae Applicatae Sinica, English Serie, 2003, 19(1): 83-86. |
|
|
|
|
2018, Vol. 34 
