0
$\begingroup$

We say that simple, undirected graphs $G, H$ are (-1)-isomorphic if there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V$ we have that the induced subgraphs $G\setminus\{v\}$ and $H\setminus\{\varphi(v)\}$ are isomorphic. (So this is a similarity notion of graphs that is weaker than isomorphism.)

For any finite or infinite graph $G = (V,E)$, we define the Hadwiger number by $$\eta(G) = \bigcup\big\{\alpha\in |V|\cup \{|V|\}: K_\alpha\text{ is a minor of }G\big\},$$ where $K_\alpha$ is the complete graph on $\alpha$ vertices.

Question. If $G, H$ are simple and undirected (-1)-isomorphic graphs with $|V(G)|, |V(H)| \geq 4$, do we necessarily have $\eta(G) = \eta(H)$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ No, a graph with two isolated vertices is (-1)-isomorphic to $K_2$. $\endgroup$
    – Tony Huynh
    Commented Dec 28, 2022 at 12:56
  • $\begingroup$ Right - this is also one of the few known counterexample to Ulam's reconstruction conjecture that states that if $G, H$ are graphs that are (-1)-isomorphic, then $G\cong H$. It is open for graphs with at least 4 points. So, I will introduce this limitation here as well $\endgroup$
    – Dominic van der Zypen
    Commented Dec 28, 2022 at 16:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .