The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the h-restricted arc-connectivity of the Harary digraph D = G(n; 1, 2, …, k) is equal to n/2 for 2≤h≤n/2, k = 2 and n is even, and λh(D) = g(k - 1) for 2≤h≤g and 3≤k <n/2, where g is the girth of D. As consequences, the super restricted arc-connectedness of Harary digraph D is obtained immediately. In particular, for k = 2 and n is even or 3≤k < n/2 and n can be divided by k, it can be determined that distinct positive (respectively, negative) λh-superatoms of D are vertex disjoint for 2≤h≤g.
Jun-Hao Zhang, Ji-Xiang Meng
. Restricted Arc-Connectivity of Harary Digraphs[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 540
-547
.
DOI: 10.1007/s40305-022-00406-8
[1] Zhu, Y.F., Zhang, Z.:Restricted connectivity of line digraphs. J. Math. Study. 43(2), 107-113(2010)
[2] Chen, Y.Y., Meng, J.X., Tian, Y.Z.:Extraconnectivity of Harary graphs. J. Xinjiang Univ. 27(1), 27-31(2010)
[3] Deng, H.Y., Li,R.H.:The optimal super-λ property of Harary graphs, Journal of Natural Science of Hunan Normal University. 27(4), 1-4(2004)
[4] Liu, Q.H., Huang,X.H., Zhang,Z.:Restricted edge connectivity of Harary graphs. Proceedings of Combinatorial Optimization and Applications-5th International Conference, COCOA 2011, Zhangjiajie, China, Springer-Verlag,(2011)
[5] Bermond, J.C., Germa, A., Heydemann, M.C.:Girth in digraphs. J. Graph Theory. 4(3), 337-341(2010)
[6] Tindell, R.:Connectivity of Cayley digraphs, In:Du, DZ., Hsu, D.F.(eds) Combinatorial Network Theory. Applied Optimization, vol 1. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-2491-2_2
[7] Hamidoune, Y.O.:Connectivité des graphes de Cayley Abeliens sans K4. Discrete Math. 83, 21-26(1990)
[8] Xu, J.M., Min, L.:On restricted arc-conectivity of regular digraphs. J. Taiwan. Math. 9(4), 661-670(2005)
