Skip to main content
added 20 characters in body
Source Link

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).

There are connected countable graphs that are isomorphic to their line graph:

  • $G=(\omega,E)$ where $E=\{\{k,k+1\}: k\in\omega\}$;
  • $G=(\mathbb{Z},E)$ where $E=\{\{k,k+1\}: k\in\mathbb{Z}\}$.

Note that in the second graph, all vertices have degree 2, which makes it into a kind of "infinite cycle". (An interesting side question would be whether these are the only connected countable graphs (up to isomorphism) that are isomorphic to their line graph.)

Question. Is there a connected graph $G=(V,E)$ with $V$ uncountable such that $G\cong L(G)$?

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).

There are countable graphs that are isomorphic to their line graph:

  • $G=(\omega,E)$ where $E=\{\{k,k+1\}: k\in\omega\}$;
  • $G=(\mathbb{Z},E)$ where $E=\{\{k,k+1\}: k\in\mathbb{Z}\}$.

Note that in the second graph, all vertices have degree 2, which makes it into a kind of "infinite cycle". (An interesting side question would be whether these are the only countable graphs (up to isomorphism) that are isomorphic to their line graph.)

Question. Is there a connected graph $G=(V,E)$ with $V$ uncountable such that $G\cong L(G)$?

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).

There are connected countable graphs that are isomorphic to their line graph:

  • $G=(\omega,E)$ where $E=\{\{k,k+1\}: k\in\omega\}$;
  • $G=(\mathbb{Z},E)$ where $E=\{\{k,k+1\}: k\in\mathbb{Z}\}$.

Note that in the second graph, all vertices have degree 2, which makes it into a kind of "infinite cycle". (An interesting side question would be whether these are the only connected countable graphs (up to isomorphism) that are isomorphic to their line graph.)

Question. Is there a connected graph $G=(V,E)$ with $V$ uncountable such that $G\cong L(G)$?

Source Link

Infinite graphs isomorphic to their line graph

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).

There are countable graphs that are isomorphic to their line graph:

  • $G=(\omega,E)$ where $E=\{\{k,k+1\}: k\in\omega\}$;
  • $G=(\mathbb{Z},E)$ where $E=\{\{k,k+1\}: k\in\mathbb{Z}\}$.

Note that in the second graph, all vertices have degree 2, which makes it into a kind of "infinite cycle". (An interesting side question would be whether these are the only countable graphs (up to isomorphism) that are isomorphic to their line graph.)

Question. Is there a connected graph $G=(V,E)$ with $V$ uncountable such that $G\cong L(G)$?