5
$\begingroup$

The line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$. $L(G)$ is constructed in the following way: for each edge in $G$, make a vertex in $L(G)$; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$.

I would like to know the crossing number of a line graph of a complete graph $K_5$. Furthermore, what is crossing-minimal drawing of $L(K_5)$?

Here's what I know now and that's about it.

  • $L(K_5)$ has crossing numer 3 or more.

We can see above result in following paper.

  • Kulli V R, Akka D G, Beineke L W. On line graphs with crossing number 1[J]. Journal of Graph Theory, 1979, 3(1): 87-90.]

Ps: We see easily that $L(K_5)$ is the complement of Petersen graph.

$\endgroup$
2
  • 3
    $\begingroup$ To compute the crossing number of a specific graph such as $L(K_5)$, you can try the CRWC. $\endgroup$ Mar 31, 2022 at 16:25
  • $\begingroup$ Thanks! I am trying to learn how to use this software. It doesn't look easy run. I tried to apply for it, but my email never received the verification message. $\endgroup$
    – lcz
    Apr 1, 2022 at 9:21

1 Answer 1

6
$\begingroup$

Thanks for advice from Timothy Chow. I have now received an email from CRWS. The graph has a crossing number of 12.

enter image description here enter image description here

Its crossing-minimal drawing is as follows. ![enter image description here

$\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.