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.

  • $\begingroup$ You would like an example with simple graphs, I assume? $\endgroup$ – Studentmath Jul 26 '14 at 8:07
  • $\begingroup$ @Studentmath Yes. $\endgroup$ – Paul Siegel Jul 26 '14 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 '14 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 '14 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 '14 at 15:10

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


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.