Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube

Details Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube

2010-09-17

arxiv.org/abs/1009.3304v1

Mathematics

Combinatorics

Scientific paper

Let $n\geq 2$ be an integer, and let $i\in\{0,...,n-1\}$. An $i$-th dimension edge in the $n$-dimensional hypercube $Q_n$ is an edge ${v_1}{v_2}$ such that $v_1,v_2$ differ just at their $i$-th entries. The parity of an $i$-th dimension edge $\edg{v_1}{v_2}$ is the number of 1's modulus 2 of any of its vertex ignoring the $i$-th entry. We prove that the number of $i$-th dimension edges appearing in a given Hamiltonian cycle of $Q_n$ with parity zero coincides with the number of edges with parity one. As an application of this result it is introduced and explored the conjecture of the inscribed squares in Hamiltonian cycles of the hypercube: Any Hamiltonian cycle in $Q_n$ contains two opposite edges in a 4-cycle. We prove this conjecture for $n \le 7$, and for any Hamiltonian cycle containing more than $2^{n-2}$ edges in the same dimension. This bound is finally improved considering the equi-independence number of $Q_{n-1}$, which is a concept introduced in this paper for bipartite graphs.

Affiliated with

Also associated with

No associations

Rating

Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parity balance of the $i$-th dimension edges in Hamiltonian cycles of the hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-441270