On the spanning connectivity and spanning laceability of hypercube-like networks

• Published in: Theoretical computer science 2007-08, Vol.381 (1), p.218-229
• Main Authors: Lin, Cheng-Kuan, Tan, Jimmy J.M., Hsu, D. Frank, Hsu, Lih-Hsing
• Format: Article
• Language: English
• Subjects: [formula omitted]-connected; [formula omitted]-laceable; Applied sciences; Computer science; control theory; systems; Exact sciences and technology; Graph container; Hamiltonian; Hamiltonian connected; Hamiltonian laceable; Hypercube networks; Hypercube-like networks; Information retrieval. Graph; Miscellaneous; Spanning connectivity; Spanning laceability; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2007.05.002

Let u and v be any two distinct nodes of an undirected graph G , which is k -connected. For 1 ≤ w ≤ k , a w - container C ( u , v ) of a k -connected graph G is a set of w -disjoint paths joining u and v . A w -container C ( u , v ) of G is a w ∗ - container if it contains all the nodes of G . A graph G is w ∗ - connected if there exists a w ∗ -container between any two distinct nodes. A bipartite graph G is w ∗ - laceable if there exists a w ∗ -container between any two nodes from different parts of G . Let G 0 = ( V 0 , E 0 ) and G 1 = ( V 1 , E 1 ) be two disjoint graphs with | V 0 | = | V 1 | . Let E = { ( v , ϕ ( v ) ) ∣ v ∈ V 0 , ϕ ( v ) ∈ V 1 , and ϕ : V 0 → V 1 is a bijection } . Let G = G 0 ⊕ G 1 = ( V 0 ∪ V 1 , E 0 ∪ E 1 ∪ E ) . The set of n -dimensional hypercube-like graph H n ′ is defined recursively as (a) H 1 ′ = { K 2 } , K 2 = complete graph with two nodes, and (b) if G 0 and G 1 are in H n ′ , then G = G 0 ⊕ G 1 is in H n + 1 ′ . Let B n ′ = { G ∈ H n ′ and G is bipartite } and N n ′ = H n ′ ∖ B n ′ . In this paper, we show that every graph in B n ′ is w ∗ -laceable for every w , 1 ≤ w ≤ n . It is shown that a constructed N n ′ -graph H can not be 4 ∗ -connected. In addition, we show that every graph in N n ′ is w ∗ -connected for every w , 1 ≤ w ≤ 3 .