Search

For any bipartite graph G with bipartition V 1 and V 2 , a t -container C t (u , v) is a set of t internally disjoint paths P 1 , P 2 , ... , P t between two vertices u ∈ V 1 and v ∈ V 2 in G , i.e., C t (u , v) = { P 1 , P 2 , ... , P t }. Moreover, if V (P 1) ∪ V (P 2) ∪ ⋯ ∪ V (P t) = V (G) then C t (u , v) is called a spanning t -container, denoted by C t s l (u , v). The length of C t s l (u , v) = { P 1 , P 2 , ... , P t } is l (C t s l (u , v)) = max { l (P i) | 1 ≤ i ≤ t }. Besides, G is spanning t -laceable if there exists a spanning t -container between any two vertices u ∈ V 1 and v ∈ V 2 in G. Assume that u ∈ V 1 and v ∈ V 2 are two distinct vertices in a spanning t -laceable graph G. Let D t s l (u , v) be the collection of all C t s l (u , v) 's. Define the spanning t -wide distance between u and v in G , d t s l (u , v) = min { l (C t s l (u , v)) | C t s l (u , v) ∈ D t s l (u , v) } , and the spanning t -wide diameter of G , D t s l (G) = max { d t s l (u , v) | u ∈ V 1 , v ∈ V 2 }. In particular, the spanning wide diameter of G is D κ s l (G) , where κ is the connectivity of G. In the paper we first provide the lower and upper bounds of the wide diameter of a bipartite graph, and then determine the exact values of the spanning wide diameters of the spider web networks S W (m , n) for n = 2 , 4. [ABSTRACT FROM AUTHOR]

One of the important issues in evaluating an interconnection network is to study the Hamiltonian cycle embedding problems. For a positive integer k, a graph G is said to be spanning k-cyclable if for k prescribed vertices x 1 , x 2 , ... , x k , there exist k disjoint cycles C 1 , C 2 , ... , C k such that the union of C 1 , C 2 , ... , C k spans G, and each C j contains exactly one vertex x j of x 1 , x 2 , ... , x k . According to the definition, the problem of finding hamiltonian cycle focuses on k = 1. The notion of spanning cyclability can be applied to the problem of identifying faulty processors and other related issues in interconnection networks. The n-dimensional augmented cube A Q n is an important node-symmetric variant of the n-dimensional hypercube Q n . In this paper, we prove that A Q n with n ≥ 3 is spanning k-cyclable for 1 ≤ k ≤ 2 n − 4. [ABSTRACT FROM AUTHOR]

Motivated by effects caused by structure link faults in networks, we study the following graph theoretical problem. Let |$T$| be a connected subgraph of a graph |$G$| except for |$K_{1}$|⁠. The |$T$| -structure edge-connectivity |$\lambda (G;T)$| (resp. |$T$| -substructure edge-connectivity |$\lambda ^s(G;T)$|⁠) of |$G$| is the minimum cardinality of a set of edge-disjoint subgraphs |$\mathcal{F}=\{T_{1},T_{2},\ldots ,T_{m}\}$| (resp. |$\mathcal{F}=\{T_{1}^{^{\prime}},T_{2}^{^{\prime}},\ldots ,T_{m}^{^{\prime}}\}$|⁠) such that |$T_{i}$| is isomorphic to |$T$| (resp. |$T_{i}^{^{\prime}}$| is a connected subgraph of |$T$|⁠) for every |$1 \le i \le m$|⁠ , and |$E(\mathcal{F})$| 's removal leaves the remaining graph disconnected. In this paper, we determine both |$\lambda (G;T)$| and |$\lambda ^{s}(G;T)$| for |$(1)$| the hypercube |$Q_{n}$| and |$T\in \{K_{1,1},K_{1,2},K_{1,3},P_{4},Q_{1},Q_{2},Q_{3}\}$|⁠ ; |$(2)$| the |$k$| -ary |$n$| -cube |$Q^{k}_{n}$|   |$(k\ge 3)$| and |$T\in \{K_{1,1},K_{1,2},K_{1,3},Q^{3}_{1},Q^{4}_{1}\}$|⁠ ; |$(3)$| the balanced hypercube |$BH_{n}$| and |$T\in \{K_{1,1},K_{1,2},BH_{1}\}$|⁠. We also extend some known results. [ABSTRACT FROM AUTHOR]