Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ vertices of degree $q$ and $p =q+r$. If $r$ is fixed and understood I write $H(r)$ to denote this graph otherwise I write $H_{q,r}$. In a previous post I showed that $H_{q,r}$ has $qr$ edges. It was also was also shown that $H_{q,r}$ is planar whenever $(q,r)$ is:
- $(1,r)$ for infinitely many $r$
- $(2,r)$ for infinitely many $r$
- $(3,r)$ for $r=4,5,6,7$ or $8$
- $(4,r)$ for $r=5$ or $r=6$
Questions:
Suppose that $H_{q,r}$ is not planar and not bipartite. $K_{q}$ is the complete graph on $q$ vertices and $K_{q,r}$ is the complete bipartite on $q$ and $r$ vertices respectively. I use $cr$ to denote the crossing number of some graph.
(1) Is it true that:
$cr(K_{q}) \leq cr(H_{q,r}) < cr(K_{q,r})$
I have by hand inspection that the crossing number of a not bipartite $H_{5,6}$ is equal to $1$. The attack is to draw $K_{5}$ and then surround it by a cycle graph on $6$ vertices and make the appropriate connections. I also have by hand inspection that the crossing number of a not bipartite $H_{5,7}=13$
(2) Can we write
$cr(H_{q,r}) = cr(K_{q}) + f(r)$ where $f(r)$ is some function on $r$.