on removal of perfect matching from folded hypercubes

2019/07/16 by S. A. Mane, Mane, S. A.
Computer Science · #Combinatorics (math.CO) #Embedded Systems Design Techniques #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1907.06951

openalex publication_date 2019/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The hypercube Qn of dimension n is one of the most versatile and powerful interconnection networks. The n-dimensional folded cube denoted as FQn, a variation of the hypercube possesses some embeddable properties that the hypercube does not possess. Dong and Wang(In Theor. Comput. Sci.771(2019)93-98) conjectured that "A subset Em of edges of FQn is a perfect matching if and only if FQn - Em is isomorphic to Qn". In this paper, we disprove this conjecture by providing some perfect matchings removal of which from FQn do not give a graph isomorphic to Qn.

Related

• On the conjecture of bijection between perfect matching and sub-hypercube in folded hypercubes
• Matchings in the hypercube with specified edges
• A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity
• Some other algebraic properties of folded hypercubes
• The minimum forcing number of perfect matchings in the hypercube