6
$\begingroup$

I am trying to see if, for the complete graph $K_{2n}$, there exists a labelling of the vertices with two labels $a$ and $b$ (each used exactly $n$ times), such that we can decompose the graph into $n$ hamiltonian paths that have the same labelling.

For example, if I take n=3, I numerate my vertices from $1$ to $6$, and associate respectively the labels $a$,$b$,$b$,$a$,$a$,$b$. Then, I take the three following paths :

$1-2-3-4-5-6$

$4-6-2-5-1-3$

$5-3-6-1-4-2$

The three paths have the same labelling and they are edge disjoint so it works.

I was able to prove the existence for $n$ odd, using Walecki's construction. For $n$ even, I know Walecki's construction does not work as the labels of the two extremities of the paths have to be different, but as I understand it is not the only construction I can use, so it does not necessarily mean that the labelling does not exist. I am leaning towards the idea that it does not exist, with the example $n=2$, but I don't see any theoretical argument to prove that. Would some of you have any ideas ? Thank you in advance.

$\endgroup$
6
  • 1
    $\begingroup$ Do you impose any restriction on the labelling? Unless I missed something, you could always just assign the same label 'a' to every vertex... ? $\endgroup$ Apr 13 '17 at 11:43
  • $\begingroup$ Is it just happenstance that in your example there are just as many $a$'s as $b$'s or is that a requirement? $\endgroup$
    – bof
    Apr 13 '17 at 11:51
  • $\begingroup$ @monkeymaths Indeed, sorry, I am imposing that there are exactly two distinct labels, so not just a's or b's. $\endgroup$
    – Alice J.
    Apr 13 '17 at 12:27
  • $\begingroup$ @bof It is necessary : since every vertex is going to play the role of an extremity exactly once, the extrimities must have distinct label, and each of them is represented exactly $n$ times, so each of the two labels is present n times. $\endgroup$
    – Alice J.
    Apr 13 '17 at 12:29
  • 1
    $\begingroup$ @bof It's not really that I add it, it is that it can not be otherwise. In $K_{2n}$ every vertex has degree $2n-1$ so that if you decompose your graph into $n$ paths, every vertex will play the role of a degree 2 vertex $n-1$ times, and the role of an extremity once. Now if the two extremities had the same label, only the vertices with the same label would be able to play the role of an extremity so it wouldn't be possible. $\endgroup$
    – Alice J.
    Apr 13 '17 at 13:06
4
$\begingroup$

I think I have a proof that such a labelling cannot exist if $n$ is even.

Suppose we have a labelling $\ell : V(K_m) \to \{ a, b \}$ and a decomposition of $K_{m}$ into a family $\mathcal{P}$ of Hamiltonian paths. It is clear by counting edges that $p := |\mathcal{P}| = m/2$, so in particular $m$ must be even. Every path $P = v_1 \ldots v_m$ in $K = K_{m}$ has a trace $\ell(v_1) \ldots \ell(v_m) \in \{ a, b \}^m$. We assume that every path in $\mathcal{P}$ has the same trace, which we denote by $T$.

Let $A$ be the set of all vertices that receive label $a$ and $B$ the set of those that receive label $b$. Suppose that neither $A$ nor $B$ is empty. Counting the edges incident to a fixed vertex, it is easy to see that every vertex is the end vertex of precisely one $P \in \mathcal{P}$. In particular, every $P \in \mathcal{P}$ has one end in $A$ and the other in $B$ and $|A| = |B| = p$ (without loss of generality, all paths start in $A$ and end in $B$).

Edited with a simplification:

Every $P \in \mathcal{P}$ has the same number $$ e_A := | \{ 1 \leq i < n : T_i = T_{i+1} = a \} | $$ of edges within $A$. Then, since every edge of $K[A]$ lies in precisely one $P \in \mathcal{P}$, we get $$ p(p-1)/2 = |E(K[A])| = pe_A $$ or $e_A = (p-1)/2$, from which it follows that $p$ must be odd.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.