Skip to main content
added 20 characters in body
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Attempt to show that itthere is not possibleno 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$.

Attempt to show that it is not possible. 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$.

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$.

Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Attempt to show that it is not possible. 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$.