Super connectivity of line graphs and digraphs

被引：0
作者：
Lü M. [1 ]
Xu J.-M. [2 ]
机构：
[1] Department of Computer Science and Technology, University of Science and Technology of China
[2] Department of Mathematics, University of Science and Technology of China
来源：
Acta Mathematicae Applicatae Sinica | 2006年 / 22卷 / 1期
基金：
中国国家自然科学基金;
关键词：
De Bruijn digraphs; Kautz digraphs; Line graphs; Super connectivity; Super edge-connectivity;
D O I：
10.1007/s10255-005-0283-2
中图分类号：
学科分类号：
摘要：
The h-super connectivity κ h and the h-super edge-connectivity λ h are more refined network reliability indices than the connectivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ 1(L) = 2λ1(D), and that for a connected graph G and its line graph L, if one of κ 1(L) and λ2(G) exists, then κ 1(L) = λ2(G). This paper determines that κ 1(B(d, n)) is equal to 4d -8 for n = 2 and d ≥ 4, and to 4d -4 for n ≥ 3 and d ≥ 3, and that κ 1(K(d, n)) is equal to 4d - 4 for d ≥ 2 and n ≥ 2 except K(2, 2). It then follows that B(d, n) and K(d, n) are both super connected for any d ≥ 2 and n ≥ 1.
引用
收藏
页码：43 / 48
页数：5
相关论文
共 15 条
  • [1] Bauer D., Boesch F., Suffel C., Tindell R., Connectivity extremal problems and the design of reliable probabilistic networks, The Theory and Application of Graphs, pp. 45-54, (1981)
  • [2] Boesch F.T., Synthesis of reliable networks-A survey, IEEE Trans. Reliability, 35, pp. 240-246, (1986)
  • [3] Esfahanian A.H., Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput., 38, 11, pp. 1586-1591, (1989)
  • [4] Esfahanian A.H., Hakimi S.L., On computing a conditional edge-connectivity of a graph, Information Processing Letters, 27, pp. 195-199, (1988)
  • [5] Fabrega J., Fiol M.A., Maximally connected digraphs, J. Graph Theory, 13, pp. 657-668, (1989)
  • [6] Fiol M.A., Fabrega J., Escudero M., Short paths and connectivity in graphs and digraphs, Ars Combin., 29 B, pp. 253-256, (1990)
  • [7] Imase M., Soneoka T., Okada K., Connectivity of regular digraphs with small diameters, IEEE Trans. Comput., 34, pp. 267-273, (1985)
  • [8] Latifi S., Hegde M., Naraghi-Pour M., Conditional connectivity measures for large miltiprocessor systems, IEEE Trans. Comput., 43, pp. 218-221, (1994)
  • [9] Meng J.X., Ji Y.H., On a kind of restricted edge connectivity of graphs, Discrete Applied Math., 117, pp. 183-193, (2002)
  • [10] Soneoka T., Super edge-connectivity of dense digraphs and graphs, Discrete Applied. Math., 37-38, pp. 511-523, (1992)
12