×

zbMATH — the first resource for mathematics

Super line-connectivity of consecutive-\(d\) digraphs. (English) Zbl 0895.05035
D.-Z. Du, D. F. Hsu and F. K. Hwang [Math. Comput. Modelling 17, No. 11, 61-63 (1993; Zbl 0789.05040)] introduced the concept of consecutive-\(d\) digraphs. A consecutive-\(d\) digraph \(G(d,n,q,r)\) has \(n\) nodes, labeled by integers \(\bmod n\), with edges from each node \(i\) to \(d\) consecutive nodes, namely those with label \(qi+r+k \pmod n\) for \(0\leq k<d \leq n\), where \(r\) and \(q\) are integers and \(-n/2<q \leq n/2\), \(q\neq 0\).
A digraph is called a modified \(G(d,n,q,r)\) if it is constructed from \(G(d,n,q,r)\) by connecting all loop-nodes into disjoint cycles of cardinality at least two and deleting all loops. Also a digraph is said to have super line-connectivity if its line-connectivity equals the minimum degree and every minimum edge-cut consists of edges incident to the same node. The authors give sufficient conditions for modified consecutive-\(d\) digraphs to have super line-connectivity.
Reviewer: M.Hager (Leonberg)

MSC:
05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bermond, J.C.; Homobono, N.; Peyrat, C., Large fault-tolerant interconnection networks, Graphs combin., (1989) · Zbl 0672.94021
[2] Bermond, J.C.; Peyrat, C., De Bruijn and kautz networks: a competitor for the hypercube?, (), 279-294
[3] Bermond, J.C.; Peyrat, C., Broadcasing in de Bruijn networks, () · Zbl 0673.94027
[4] Bermond, J.C.; Homobono, N.; Peyrat, C., Connectivity of kautz networks, () · Zbl 0782.05053
[5] Bond, J.; Ivanyi, A., Modeling of interconnection networks using de Bruijn graphs, (), 75-88
[6] de Bruijn, N.G., A combinatorial problem, koninklijke nederlandse Academic Van wetenschappen, (), 758-764 · Zbl 0060.02701
[7] Chung, F.K., Diameter of communication networks, (), 1-18
[8] Du, D.-Z.; Hsu, D.F.; Hwang, F.K., Doubly-linked ring networks, IEEE trans. comput., C-34, 853-855, (1985)
[9] Du, D.-Z.; Hsu, D.F., On Hamiltonian consecutive-d digraphs, (), 47-55, Warsaw · Zbl 0729.05022
[10] Du, D.-Z.; Hsu, D.F.; Hwang, F.K., Hamiltonian property of d-consecutive digraphs, Math. comput. modeling, 17, 11, 61-63, (1993) · Zbl 0789.05040
[11] Du, D.-Z.; Hsu, D.F.; Hwang, F.K.; Zhang, X.M., The Hamiltonian property of generalized de Bruijn digraphs, J. combin. theory, ser. B, 52, 1-8, (1991) · Zbl 0736.05039
[12] Du, D.-Z.; Hsu, D.F.; Kleitman, D.J., Modifications of consecutive-d digraphs, (), 75-85 · Zbl 0837.05079
[13] D.-Z. Du, D.F. Hsu, D.J. Kleitman, On connectivity of consecutive-d digraphs, manuscript.
[14] Du, D.-Z.; Hsu, D.F.; Peck, G.W., Connectivity of consecutive-d digraphs, Discrete appl. math., 37/38, 169-177, (1992) · Zbl 0776.05045
[15] Du, D.-Z.; Hwang, F.K., Generalized de Bruijn digraphs, Networks, 18, 27-33, (1988) · Zbl 0654.05036
[16] Fiol, M.A.; Yebra, J.L.A.; Alegre, I., Line digraph iterations and the (d,k) digraph problem, IEEE trans. comput., C-33, 702-713, (1984)
[17] Hamidoune, Y.O.; Llado, A.S.; Serra, O., Vosperian and superconnected abelian Cayley digraphs, Graphs combin., 7, 143-152, (1991) · Zbl 0736.05047
[18] Homobono, N., Connectivity of generalized de Bruijn and kautz graphs, ()
[19] Homobono, N.; Peyrat, C., Connectivity of imase and itoh digraphs, () · Zbl 0659.68091
[20] Hsu, D.F., On container width and length in graphs, groups, and networks, (), 668-680
[21] Hwang, F.K., The Hamiltonian property of linear functions, Oper. res. lett., 6, 125-127, (1987) · Zbl 0615.05033
[22] Imase, M.; Itoh, M., Design to minimize a diameter on building block network, IEEE trans. comput., C-30, 439-443, (1981) · Zbl 0456.94030
[23] Imase, M.; Itoh, M., A design for directed graph with minimum diameter, IEEE trans. comput., C-32, 782-784, (1983) · Zbl 0515.94027
[24] Imase, M.; Soneoka, T.; Okada, K., Connectivity of regular directed graphs with small diameter, IEEE trans. comput., C-34, 267-273, (1985) · Zbl 0554.05044
[25] Imase, M.; Soneoka, I.; Okada, K., A fault tolerant processor interconnection network, Systems and computers in Japan, 17, 8, 21-30, (1986)
[26] Kautz, W.H., Bounds on directed (d, k) graphs, theory of cellular logic networks and machines, AFCRL-68-0668 final report, 20-28, (1968)
[27] Kumar, V.P.; Reddy, S.M., A class of graphs for fault-tolerant processor interconnections, (), 448-460
[28] Mora, M.; Serra, O.; Fiol, M.A., General properties of c-circulant digraphs, Ars combin., 25C, 241-252, (1988) · Zbl 0648.05024
[29] Reddy, S.M.; Kuhl, J.G.; Hosseini, S.H.; Lee, H., On digraphs with minimum diameter and maximum connectivity, (), 1018-1026
[30] Reddy, S.M.; Pradhan, D.K.; Kuhl, J.G., Directed graphs with minimal diameter and maximal connectivity, School of engineering Oakland univ. tech. rep., (1980)
[31] Soneoka, T.; Nakada, H.; Imase, M., Design of d-connected digraph with a minimum number of edges and a quasiminimal diameter I, Discrete appl. math., 27, 255-265, (1990) · Zbl 0707.05027
[32] Soneoka, T.; Imase, M.; Manabe, Y., Design of d-connected digraph with a minimum number of edges and a quasiminimal diameter II, Discrete appl. math., 64, 267-279, (1996) · Zbl 0848.05034
[33] T. Soneoka, Super edge-connectivity of dense digraphs and graphs, manuscript. · Zbl 0760.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.