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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 8, 2016 at 22:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .