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.
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)
Citations:
Zbl 0789.05040References:
| [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?, (Andre, F.; Verjus, J. P., Hypercube and Distributed Computers (1989), North-Holland,: North-Holland, Amsterdam), 279-294 |
| [3] | Bermond, J. C.; Peyrat, C., Broadcasing in de Bruijn networks, (Proc. 19th Southeastern Conf. on Combinatorics, Graph Theory and Computing (1988)) · Zbl 0673.94027 |
| [4] | Bermond, J. C.; Homobono, N.; Peyrat, C., Connectivity of Kautz networks, (French-Israel Conf. on Combinatorics. French-Israel Conf. on Combinatorics, Jerusalem (1988)) · Zbl 0782.05053 |
| [5] | Bond, J.; Ivanyi, A., Modeling of interconnection networks using de Bruijn graphs, (Vitanyi, A., Proc. 3rd Conf. of Program Designers. Proc. 3rd Conf. of Program Designers, Budapest (1987)), 75-88 |
| [6] | de Bruijn, N. G., A combinatorial problem, Koninklijke Nederlandse Academic van Wetenschappen, (Proc. A, 49 (1946)), 758-764 · Zbl 0060.02701 |
| [7] | Chung, F. K., Diameter of communication networks, (Proc. Symp. in Applied Mathematics, 34 (1986)), 1-18 · Zbl 0595.94025 |
| [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, (Combinatorics and Graph Theory. Combinatorics and Graph Theory, Banach Center Publication, vol. 25 (1989)), 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, (Hsu, D. F.; Rosenberg, A. L.; Soteau, D., Interconnection Networks and Mapping and Scheduling Parallel Computations (1994), American Mathematical Society,: American Mathematical Society, Providence, RI), 75-85 · Zbl 0837.05079 |
| [13] | D.-Z. Du, D.F. Hsu, D.J. Kleitman, On connectivity of consecutive-\(d\); D.-Z. Du, D.F. Hsu, D.J. Kleitman, On connectivity of consecutive-\(d\) |
| [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, (Proc. 11th British Conf., Ars Combin. (1988)) |
| [19] | Homobono, N.; Peyrat, C., Connectivity of Imase and Itoh digraphs, (IEEE Trans. Comput. (1988)) · Zbl 0659.68091 |
| [20] | Hsu, D. F., On container width and length in graphs, groups, and networks, (IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences E77-A:4 (1994)), 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, (IEEE 1984 Int. Conf. Distributed Computing Systems (1984)), 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, (Proc. 20th Annual Allerton Conf. (1982)), 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.; 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
