Mutually independent bipanconnected property of hypercube

摘要

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v0, v1, … , vm〉 is a sequence of adjacent vertices. Two paths with equal length P1 = 〈 u1, u2, … , um〉 and P2 = 〈 v1, v2, … , vm〉 from a to b are independent if u1 = v1 = a, um = vm = b, and ui ≠ vi for 2 ⩽ i ⩽ m − 1. Paths with equal length {Pi}i=1n from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, dG(u, v) ⩽ l ⩽ ∣V(G) − 1∣ with (l − dG(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths Pili=1m with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with dQn(u,v)⩾n-1, is (n − 1, l)-mutually independent bipanconnected for every l,dQn(u,v)⩽l⩽|V(Qn)-1| with (l-dQn(u,v)) being even. As for dQn(u,v)⩽n-2, it is also (n − 1, l)-mutually independent bipanconnected if l⩾dQn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=dQn(u,v).