For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows:

  • $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b \big\}$;
  • $E(L(K_n)) = \big\{\{x,y\}: x,y\in V(L(K_n)) \text{ and } x\cap y \neq \emptyset\big\}$.

For any graph $G=(V,E)$ the Hadwiger number $\eta(G)$ is the largest $n\in \omega$ such that $K_n$ is a minor of $G$.

In this post it is shown that $\eta(L(K_5)) \geq 6$, and it's easy to see that $\eta(L(K_n)) \geq n+1$ for $n\geq 5$.

Question: Given a positive integer $k\in\mathbb{N}$, is there $n\in \mathbb{N}$ such that $\eta(L(K_n)) \geq k\cdot n$?

  • $\begingroup$ You have $K_5$ in the expression following "easy to see" which seems wrong. $\endgroup$ – Gordon Royle Apr 13 '15 at 10:25

Claim. For all even $n \geq 4$, $\eta(L(K_n)) \geq \frac{3n-4}{2}$ and for all odd $n \geq 3, \eta(L(K_n)) \geq \frac{3n-3}{2}$

Proof. A clique-minor of size $k$ in $L(K_n)$ corresponds to $k$ edge-disjoint connected subgraphs of $K_n$ which pairwise intersect.

Let $n$ be even. For our $\frac{3n-4}{2}$ subgraphs we first take the $n-1$ edges of a star centered at $x$. By an old theorem of Walecki, the edges of $K_n-x$ can be decomposed into Hamiltonian cycles. There are $\frac{1}{2}(n-2)$ such cycles, giving us $\frac{3n-4}{2}$, as required.

For $n$ odd, we use the same argument but take a Hamiltonian path decomposition of $K_n-x$ instead.

  • $\begingroup$ Thanks - can you extend this argument to show that for some $n\in\mathbb{N}$ we have $L(K_n) \geq 2n$? (Sorry - I have edited the original question to make it more precise.) $\endgroup$ – Dominic van der Zypen Apr 13 '15 at 11:31
  • $\begingroup$ You're welcome. Sorry, off the top of my head I don't see how to get a lower bound of $2n$. I'll give it some thought when I get a chance. $\endgroup$ – Tony Huynh Apr 15 '15 at 13:00

Here is an idea for a yes answer: put $k$ walkers at every vertex. Order the edges randomly, and also randomly pick an orientation on each edge randomly. Now in order, walk the walker across the current edge who has been sitting at the starting vertex the longest (if the vertex has at least one walker). This should give $kn$ edge-disjoint walks of length $\sim \frac{n}{2k}$ which look very similar to random walks, so they should pairwise intersect.

  • $\begingroup$ That's a good start. Any proof of this would be appreciated! $\endgroup$ – Dominic van der Zypen Apr 18 '15 at 7:02

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.