7
$\begingroup$

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)$?

$\endgroup$
4
  • $\begingroup$ That's right - > just edited $\endgroup$ Commented Jan 23, 2015 at 9:10
  • $\begingroup$ Regarding the side question, the complete graph with a countable number of vertices is isomorphic to its line graph. $\endgroup$ Commented Jan 23, 2015 at 19:59
  • $\begingroup$ I'm wondering if maybe your real question is about graphs of bounded degree? $\endgroup$ Commented Jan 23, 2015 at 20:10
  • 3
    $\begingroup$ @TimothyChow: It is not hard to see that if $G\cong L(G)$ and $G$ has a vertex of degree at least 3, then $G$ has a vertex of degree at least $n$ for all $n\in\mathbb{N}$. Basically, start with a graph with a vertex of degree 3 and one more connected edge and then iterate the operation $L$; all the graphs obtained from this must embed in $G$, but they have vertices of arbitrarily high degree. $\endgroup$ Commented Jan 24, 2015 at 2:34

1 Answer 1

6
$\begingroup$

Note first that $L$ is naturally an endofunctor on the category of graphs and injective graph-homomorphisms that commutes with filtered colimits. Let $G$ be any graph such that there is an embedding $i:G\to L(G)$. This gives rise to an embedding $L(i):L(G)\to L(L(G))$, an embedding $L(L(i)):L(L(G))\to L(L(L(G)))$, and so on. Let $L^\omega(G)$ be the colimit of $G\to L(G)\to L(L(G))\to \dots$. Since $L$ commutes with filtered colimits, there are canonical isomorphisms $$L(L^\omega(G))\cong L(\varinjlim(G\to L(G)\to\dots))\cong \varinjlim( L(G)\to L(L(G))\to\dots)\cong L^\omega(G).$$

Furthermore, if $G$ is connected, so is $L^\omega(G)$, and if $G$ is infinite, $L^\omega(G)$ has the same cardinality as $G$. Thus to get a connected graph of a given infinite cardinality isomorphic to its line graph, it suffices to give a connected graph $G$ of that cardinality that embeds in $L(G)$. But this is easy; for instance, complete graphs work. In fact, any connected graph whose cardinality $\kappa$ has uncountable cofinality works, since such a graph must contain a vertex of degree $\kappa$, and thus $L(G)$ contains a clique of size $\kappa$.

$\endgroup$
2
  • 2
    $\begingroup$ A connected graph of cardinality $\aleph_\omega$ does not necessarily have a vertex of degree $\aleph_\omega$. $\endgroup$
    – bof
    Commented Jan 23, 2015 at 9:35
  • $\begingroup$ bof: Thanks, corrected. @Carl: $L(G)$ is not complete, but it contains a complete subgraph of the same size (all the edges containing some particular vertex). $\endgroup$ Commented Jan 23, 2015 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.