zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. (English) Zbl 1115.68116
Summary: We deal with the graph $G_0 \oplus G_1$ obtained from merging two graphs $G_0$ and $G_1$ with n vertices each by $n$ pairwise nonadjacent edges joining vertices in $G_0$ and vertices in $G_1$. The main problems studied are how fault-panconnectivity and fault-pancyclicity of $G_0$ and $G_1$ are translated into fault-panconnectivity and fault-pancyclicity of $G_0 \oplus G_1$, respectively. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of $G_0 \oplus G_1$ connecting two lower dimensional networks $G_0$ and $G_1$. Applying our results to a class of hypercube-like interconnection networks called restricted HL-graphs, we show that in a restricted HL-graph $G$ of degree $m (\geq 3)$, each pair of vertices are joined by a path in $G\backslash F$ of every length from $2m-3$ to $|V(G\backslash F)|-1$ for any set $F$ of faulty elements (vertices and/or edges) with $|F|\leq m-3$, and there exists a cycle of every length from 4 to $|V(G\backslash F)|$ for any fault set $F$ with $|F|\leq m-2$.

68R10Graph theory in connection with computer science (including graph drawing)
Full Text: DOI
[1] Araki, T.: Edge-pancyclicity of recursive circulants. Inform. proc. Lett. 88, 287-292 (2003) · Zbl 1178.68022
[2] Araki, T.; Shibata, Y.: Pancyclicity of recursive circulant graphs. Inform. proc. Lett. 81, 187-190 (2002) · Zbl 1013.68137
[3] Bondy, J. A.; Murty, U. S. R.: Graph theory with applications. (1976) · Zbl 1226.05083
[4] Chang, J. -M.; Yang, J. -S.; Wang, Y. -L.; Cheng, Y.: Panconnectivity, fault-tolerant hamiltonicity and Hamiltonian-connectivity in alternating group graphs. Networks 44, 302-310 (2004) · Zbl 1055.05076
[5] Chedid, F. B.: On the generalized twisted cube. Inform. proc. Lett. 55, 49-52 (1995) · Zbl 0875.68142
[6] P. Cull, S. Larson, The Möbius cubes, in: Proc. of the 6th IEEE Distributed Memory Computing Conf., 1991, pp. 699--702 · Zbl 1041.68522
[7] Efe, K.: A variation on the hypercube with lower diameter. IEEE trans. Comput. 40, No. 11, 1312-1316 (1991)
[8] Efe, K.: The crossed cube architecture for parallel computation. IEEE trans. Parallel distributed syst. 3, No. 5, 513-524 (1992)
[9] Esfahanian, A. -H.; Ni, L. M.; Sagan, B. E.: The twisted n-cube with application to multiprocessing. IEEE trans. Comput. 40, No. 1, 88-93 (1991)
[10] Fan, J.: Hamilton-connectivity and cycle-embedding of the Möbius cubes. Inform. proc. Lett. 82, 113-117 (2002) · Zbl 1013.68008
[11] J. Fan, X. Lin, X. Jia, R.W.H. Lau, Edge-pancyclicity of twisted cubes, in: Proc. of International Symposium on Algorithms and Computation ISAAC 2005, December 2005, pp. 1090--1099 · Zbl 1175.68291
[12] Fan, J.; Lin, X.; Jia, X.: Node-pancyclicity and edge-pancyclicity of crossed cubes. Inform. proc. Lett. 93, 133-138 (2005) · Zbl 1169.05339
[13] Hilbers, P. A. J.; Koopman, M. R. J.; Van De Snepscheut, J. L. A.: The twisted cube. Parallel architectures, 152-159 (1987)
[14] S.-Y. Hsieh, N.-W. Chang, Cycle embedding on the Möbius cube with both faulty nodes and faulty edges, in: Proc. of 11th International Conference on Parallel and Distributed Systems ICPADS 2005, 2005
[15] Latifi, S.; Bagherzadeh, N.; Gajjala, R. R.: Fault-tolerant embedding of linear arrays and rings in the star graph. Comput. elect. Eng. 23, No. 2, 95-107 (1997)
[16] Li, T.: Cycle embedding in star graphs with edge faults. Appl. math. Comput. 167, 891-900 (2005) · Zbl 1075.05047
[17] Ma, M.; Xu, J. -M.: Panconnectivity of locally twisted cubes. Appl. math. Lett. 19, 673-677 (2006) · Zbl 1118.05050
[18] Mcsorley, J. P.: Counting structures in the Möbius ladder. Discrete math. 184, No. 1--3, 137-164 (1998) · Zbl 0957.05057
[19] Park, C. -D.; Chwa, K. Y.: Hamiltonian properties on the class of hypercube-like networks. Inform. proc. Lett. 91, 11-17 (2004) · Zbl 1178.68043
[20] Park, J. -H.: Cycle embedding of faulty recursive circulants. J. kiss 31, No. 2, 86-94 (2004)
[21] Park, J. -H.; Chwa, K. Y.: Recursive circulants and their embeddings among hypercubes. Theoret. comput. Sci. 244, 35-62 (2000) · Zbl 0945.68003
[22] J.-H. Park, H.-C. Kim, H.-S. Lim, Fault-hamiltonicity of hypercube-like interconnection networks, in: Proc. of IEEE International Parallel and Distributed Processing Symposium IPDPS 2005, Denver, Apr. 2005
[23] Park, J. -H.; Kim, H. -C.; Lim, H. -S.: Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE trans. Parallel distributed syst. 17, No. 3, 227-240 (2006)
[24] Sengupta, A.: On ring embedding in hypercubes with faulty nodes and links. Inform. proc. Lett. 68, 207-214 (1998)
[25] N.K. Singhvi, K. Ghose, The Mcube: A symmetrical cube based network with twisted links, in: Proc. of the 9th IEEE Int. Parallel Processing Symposium IPPS 1995, 1995, pp. 11--16
[26] A.S. Vaidya, P.S.N. Rao, S.R. Shankar, A class of hypercube-like networks, in: Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing SPDP 1993, December 1993, pp. 800--803
[27] Yang, X.; Evans, D. J.; Megson, G. M.: The locally twisted cubes. Int. J. Comput. math. 82, No. 4, 401-413 (2005) · Zbl 1097.68522
[28] Yang, M. -C.; Li, T. -K.; Tan, J. J. M.; Hsu, L. -H.: Fault-tolerant cycle-embedding of crossed cubes. Inform. proc. Lett. 88, 149-154 (2003) · Zbl 1178.68092
[29] Yang, M. -C.; Li, T. -K.; Tan, J. J. M.; Hsu, L. -H.: On embedding cycles into faulty twisted cubes. Inform. sci. 176, 676-690 (2006) · Zbl 1103.68028