8
$\begingroup$

Let $G$ and $H$ be graphs on the vertex set $\{1, \ldots, n\}$ and let $(e_i)$ be the standard basis of $\mathbb{R}^n$. For each edge $\{i,j\}$ define edge vectors $e_i - e_j$ and $e_j - e_i$ in $\mathbb{R}^n$.

Question 1: If there is a linear isomorphism of $\mathbb{R}^n$ with itself that takes the edge vectors of $G$ bijectively onto the edge vectors of $H$, must $G$ and $H$ be isomorphic?

The answer to this question is no: if $G$ and $H$ are both trees then there is such a linear isomorphism. Aside from $e_i - e_j$ being the negation of $e_j - e_i$, there are no linear dependences among the edge vectors, and the edge vectors of $G$ can be mapped to the edge vectors of $H$ in any manner.

Question 2: Same as Question 1, but now assuming that $G$ and $H$ both have central vertices, i.e., each of them has a vertex which is adjacent to every other vertex.

I assumed a counterexample to Question 1 would easily yield a counterexample to Question 2, but I don't see this. A counterexample to Question 2 is what I need.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Hm, is it possible? Whitney 2-isomorphism theorem (see e.g. www-ma2.upc.edu/demier/tesidina4.pdf ) provides all possible examples of graphs with isomorphic cyclic matroids (this is a priori even bit weaker that what you are asking for), but it rarely produces central vertices. $\endgroup$
    – Fedor Petrov
    Mar 8, 2016 at 16:32
  • 2
    $\begingroup$ To be more specific. Assume that we have two graphs $G_1$, $G_2$ on disjoint sets $V_1,V_2$, vertices $v_1,u_1\in V_1$; $v_2,u_2\in V_2$. We may glue $v_1$ with $v_2$ and $u_1$ with $u_2$, so take graph $H$, and we may instead glue $v_1$ with $u_2$ and $u_1$ with $v_2$, so take graph $K$. Cycle matroids of $H$ and $K$ are isomorphic. Whitney's theorem that if two graphs are isomorphic, then they may be obtained one from another by a sequence of such twists. $\endgroup$
    – Fedor Petrov
    Mar 8, 2016 at 16:39
  • 1
    $\begingroup$ (cont.) Note that if $H$ and $K$ both have central vertices, they are isomorphic by obvious reasons. But the problem is that intermediate graph may have not central vertices, while first and final graphs somehow have it. $\endgroup$
    – Fedor Petrov
    Mar 8, 2016 at 16:40
  • $\begingroup$ It seems such a linear map induces a bijection on cycles of the two graphs (but I have no proof). Running with this premise, I see two possibilities: Try two non-isomorphic regular graphs and augment each with a central vertex and see what you get for a counterexample; assume no cex exists for question two, focus on polytime algorithms to finding a linear isomorphism, and use this to one-up Babai with a polytime solution for the hard part of GI. Gerhard "In A Friendly, Way, Naturally" Paseman, 2016.03.08. $\endgroup$
    – Gerhard Paseman
    Mar 8, 2016 at 17:02
  • $\begingroup$ @Gerhard Of course, cycles correspond to cycles, since being a cycle is equivalent to being linearly dependent. $\endgroup$
    – Fedor Petrov
    Mar 8, 2016 at 17:19

1 Answer 1

Reset to default
2
$\begingroup$

Attempt to show that there is no example for Question 2.

Let $G$ be a graph with central vertex $v_0$, $H$ be a graph with central vertex $u_0$ and cycle structures (cyclic matroids) of $G$ and $H$ are isomorphic. I claim that $H$ and $G$ themselves are isomorphic as graphs. Let $T$ be a spanning tree in $G$ formed by edges incident to $v_0$. It corresponds to some spanning tree $f(T)$ in $H$, here $f$ is an isomorphism of matroids (so, $f$ is defined on edges of $G$). Note that in $G$ any edge $e\notin T$ belongs to a triangle with two edges from $T$. Thus the same holds in $H$. Apply this to edges in $H$ incident to $u_0$ but not coming from $u_0$. We see that maximal path in $f(T)$ going from $u_0$ consists at most two edges. Let $u_0u_1,\dots,u_0u_k$ be edges incident to $u_0$ and belonging to $f(T)$, $v_0v_i$ be their $f$-preimages. Next, if $u_i$, $1\leqslant i\leqslant k$, is incident to some edge $u_iu_m\in f(T)$, $m>k$, then denote by $v_0v_m$ $f$-preimage of the edge $u_0u_m\in H$. Then $v_i\rightarrow u_i,i=0,1,\dots$ is isomorphism of $G$ and $H$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think this works. Really nice! $\endgroup$
    – Nik Weaver
    Mar 8, 2016 at 22:38

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.