0
$\begingroup$

I am taking a course on Graph Theory in the upcoming semester so I started reading through Bondy and Murty.

Would rotating a graph that is an isomorphism of two graphs still count as another isomorphism, albeit not the most imaginative one? Or am I completely missing the point of this exercise by just wanting to take this lazy solution?

Edit: Isomorphic graphs are graphs that are the same in structure, their edges and vertices, but differ in labels. The exercise itself says to find another isomorphism, so another way of redrawing the set of edges and vertices, between two graphs that are given.
I omitted the exercise because I thought my question wasn't dependent on it as I also didn't think providing the given graphs for the exercise was necessary either. This is my first post on StackExchange so please be patient.

Thanks.

$\endgroup$
  • $\begingroup$ I don't know what you mean by "a graph that is an isomorphism of two other graphs". In what sense is a graph an isomorphism? $\endgroup$ – user247327 Aug 8 '18 at 19:08
  • $\begingroup$ You haven't given the statement of the exercise that you are working on. Without knowing the statement of that exercise, it is hard to know if you are missing the point or not. It might also be helpful if you defined a "rotation of a graph" (typically, graphs don't have an inherent orientation, though their embeddings into, say, $\mathbb{R}^2$ can provide an orientation). A workable definition of a "graph isomorphism" would also be helpful. $\endgroup$ – Xander Henderson Aug 8 '18 at 19:11
  • $\begingroup$ Yes, some graph isomorphisms look like rotations. For example, for the graph $\{a,b,c\}$ with no edges then sending $f(a)=b,f(b)=c,f(c)=a$ is a graph isomorphism, and it looks like the vertices were rotated. If the graph had a single edge $(b,c)$, then the same mapping of vertices wouldn't be an isomorphism. If the same set of vertices had all possible edges $(a,b),(a,c),(b,c)$, then the rotation would again be an isomorphism. $\endgroup$ – user582578 Aug 8 '18 at 19:21
  • $\begingroup$ Regarding the edit: Well, as you see from my examples above, whether the same 'rotation of vertices' is an isomorphism or not does depend on the particular graph, on what are its edges. $\endgroup$ – user582578 Aug 8 '18 at 19:39
  • $\begingroup$ Write out the adjacency matrix of the graph. An isomorphism of a graph is a permutation of the rows and columns in its adjacency matrix (i.e. a relabelling of vertices) that leaves the adjacency matrix unchanged. $\endgroup$ – gandalf61 Aug 8 '18 at 19:53
1
$\begingroup$

An isomorphism of graphs $G$ and $H$ is a function $f:V(G)\to V(H)$ that preserves adjacencies and non-adjacencies. Two graphs are said to be isomorphic if there exists an isomorphism.

Imagine $G$, a 4-cycle imbedded in the plane, as a square whose vertices are labeled $1,2,3,$ and $4$ clockwise from the upper left vertex. If we have another 4-cycle $H$ that is also imbedded as a square and whose vertices are labeled clockwise $1,2,3$ and $4$ starting with the upper right vertex, then the identity map serves as a natural isomorphism for these two graphs. Observe that $H$ is simply $G$ rotated by $90^{\circ}$.

$\endgroup$

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.