5
$\begingroup$

This is an extension of a previous question: https://math.stackexchange.com/questions/876336/is-a-graph-uniquely-determined-by-its-weighted-2-step-graph/876357#876357. In that question I asked about arbitrary graphs; in this question I restrict to connected graphs. Here are the details:

Let $G$ be an undirected graph. Define the 2-step graph $G^{(2)}$ of $G$ to be the weighted graph whose vertices are the same as those of $G$ but whose edges correspond to 2-step paths in $G$. Thus the weight of an edge $(u,v)$ is the number of distinct vertices $w$ such that $(u,w)$ and $(w,v)$ are both edges in $G$. (In particular, the weight of $(u,u)$ is the degree of $u$ for every vertex $u$.) My question:

Are there two connected, non-isomorphic graphs $G$ and $H$ such that $G^{(2)}$ is isomorphic to $H^{(2)}$?

My intuition says that the answer should be "yes", but I'm unable to construct an example.

Improve this question
$\endgroup$
9
  • $\begingroup$ You would like an example with simple graphs, I assume? $\endgroup$
    – Studentmath
    Jul 26, 2014 at 8:07
  • $\begingroup$ @Studentmath Yes. $\endgroup$
    – Paul Siegel
    Jul 26, 2014 at 8:14
  • $\begingroup$ If connected graphs were so easily determined, the isomorphism problem for them would be decided in polynomial time --- but that's widely believed to be impossible, so surely there are counterexamples. $\endgroup$
    – Gerry Myerson
    Jul 26, 2014 at 8:53
  • $\begingroup$ Correct me if I am wrong, but this is equivalent to asking whether two different irreducible, 0-1 matrices may have the same equivalent $A^2$ matrix? $\endgroup$
    – Studentmath
    Jul 26, 2014 at 8:56
  • 2
    $\begingroup$ @GerryMyerson Do you have a specific polynomial time algorithm in mind for determining whether or not the $2$-step graphs are isomorphic? As far as I can tell the isomorphism problem for the $2$-step graphs is just as hard (maybe harder?) than the isomorphism problem for the original graphs. $\endgroup$
    – Paul Siegel
    Jul 26, 2014 at 15:10

1 Answer 1

Reset to default
3
$\begingroup$

A counterexample can be constructed as follows. Let $G$ be the graph of a hexagonal pyramid and $H$ be that of a pair of tetrahedra sharing one common vertex. Then, $G^2$ and $H^2$ are isomorphic while $G$ and $H$ themselves are not. Indeed, $G$ has a simple $6$-cycle but $H$ has not. enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.