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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ To compute the crossing number of a specific graph such as $L(K_5)$, you can try the CRWC. $\endgroup$
    – Timothy Chow
    Commented 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$
    – Licheng Zhang
    Commented Apr 1, 2022 at 9:21

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .