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
    Commented Jul 26, 2014 at 8:07
  • $\begingroup$ @Studentmath Yes. $\endgroup$
    – Paul Siegel
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

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