On 4-regular 4-connected bipancyclic subgraphs of hypercubes
Y. M. Borse, S. R. Shaikh · Discrete Mathematics Algorithms and Applications · 2017
We consider the problem of determining the possible orders for [Formula: see text]-regular, [Formula: see text]-connected and bipancyclic subgraphs of the hypercube [Formula: see text] For [Formula: see text] and [Formula: see text] the solution to the problem is known. In this paper, we solve the problem for [Formula: see text] by proving that [Formula: see text] has a 4-regular, 4-connected and bipancyclic subgraph on [Formula: see text] vertices if and only if [Formula: see text] or [Formula: see text] is an even integer such that [Formula: see text] Further, by improving a result of Ramras, we prove that a [Formula: see text]-regular subgraph of [Formula: see text] is either isomorphic to [Formula: see text] or has at least [Formula: see text] vertices. We also improve a result of Mane and Waphare regarding the existence of a [Formula: see text]-regular, [Formula: see text]-connected and bipancyclic subgraph of [Formula: see text] Some applications of our results are given.