0
$\begingroup$

If $G=(V,E)$ is a finite, simple, undirected graph, the Hadwiger number $\eta(G)$ is defined to be the size of the largest complete minor of $G$.

Is there a finite graph $G=(V,E)$ with the following property?

Whenever $v,w\in V$ have distance $2$, the Hadwiger number of the graph obtained by collapsing $v,w$ is strictly larger than $\eta(G)$.

$\endgroup$
1
$\begingroup$

Well, if you collapse all vertices of distance 2 in a connected graph, then the resulting graph will either be a single vertex (if the graph is not bipartite) or an edge.

But there are graphs where you can identify some of the vertices of distance 2 from each other to increase $\eta(G)$.

Indeed,

  1. First let $G$ be a $K+1$-clique where $K$ is of the form e.g. $K=d(d-1)$ for some integer $d \geq 3$.

  2. Now subdivide each edge in $G$ to a path with say 5 vertices and call the resulting graph $G'$. Then every vertex of degree greater than 2 in $G'$ has degree $K$, and $\eta(G)$ is still $K+1$.

  3. Now replace every vertex $v$ in $G'$ of degree $K$ with a complete $d$-ary tree $T_v$ with $K=d(d-1)$ leaves and write the set of $K$ leafs in $T_v$ as $\{u_{vv'}; v'$ another vertex in $G'$ of degree $K\}$--for every two vertices $v,v'$ of degree $K$ in $G'$, there is now a path from $u_{vv'}$ of $T_v$ to $u_{v'v}$ of $T_{v'}$ (every vertex and edge in the interior of this past is the same in $H$ as it was in $G'$). Call the resulting graph $H$.

  4. Then $\eta(H) \le d < K < \eta(G)$. However, identifying in $H$ all vertices of distance 2 in each of the $T_v$s results in a graph that is close enough to $G'$ and as rthe same Hadwiger number as $G'$. Indeed this collapses each $T_v$ to an edge where one endpoint has degree $K$ (and the other endpoint is incident to no more edges). In fact this resulting graph has $G'$ as a subgraph--indeed every vertex of degree $K$ in $G'$ is incident to another edge where the endpoint is an isolated vertex.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer! My question was not, what happens if I identify all vertices that have distance $2$, but my question was: what is an example of a graph $G=(V,E) $ such that *whenever* I pick $v,w\in V$ such that $v,w$ have distance $2$, then the Hadwiger number is increased. Should I reformulate the question? $\endgroup$ – Dominic van der Zypen Feb 4 '19 at 7:42
  • $\begingroup$ Just edited the question to (hopefully) make it clearer $\endgroup$ – Dominic van der Zypen Feb 4 '19 at 7:45

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.