The Mutually Independent Edge-Bipancyclic Property in Hypercube Graphs

Abstract

A graph G is edge-pancyclic if each edge lies on cycles of all lengths. A bipartite graph is edgebipancyclic if each edge lies on cycles of every even length from 4 to jV (G)j. Two cycles with the same length m, C1 = hu1; u2; ¢ ¢ ¢ ; um; u1i and C2 = hv1; v2; ¢ ¢ ¢ ; vm; v1i passing through an edge (x; y) are independent with respect to the edge (x; y) if u1 = v1 = x, um = vm = y and ui 6= vi for 2 · i · m¡1. Cycles with equal length C1;C2; ¢ ¢ ¢ ;Cn passing through an edge (x; y) are mutually independent with respect to the edge (x; y) if each pair of them are independent with respect to the edge (x; y). We propose a new concept called mutually independent edge-bipancyclicity. We say that a bipartite graph G is k-mutually independent edge-bipancyclic if for each edge (x; y) 2 E(G) and for each even length l, 4 · l · jV (G)j, there are k cycles with the same length l passing through edge (x; y), and these k cycles are mutually independent with respect to the edge (x; y). In this paper, we prove that the hypercube Qn is (n¡1)-mutually independent edge-bipancyclic for n ¸ 4.