Skip to main content
edited body
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bithboth graphs by a vertex connected to all vertices.

The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bith graphs by a vertex connected to all vertices.

The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting both graphs by a vertex connected to all vertices.

deleted 1 character in body
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

The answer to the secondfirst question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bith graphs by a vertex connected to all vertices.

The answer to the second question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bith graphs by a vertex connected to all vertices.

The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be a multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bith graphs by a vertex connected to all vertices.

Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

The answer to the second question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ and $ebgd$.

The answer for the second question is also positive, even if we consider $\mathcal H(G)$ to be multi-hypergraph (thus taking neighborhoods with multiplicities). Take any connected non-bipartite graph $G$ and construct two graphs from it: first one is the disjoint union of two copies of $G$, another one is the tensor product of $G$ with an edge. Both have the same neighborhood multi-hypergraph, but one is not connected and another one is.

If you need, say, only connected graphs you may also obtain such by augmenting bith graphs by a vertex connected to all vertices.