The exact crossing number is only known for a small number of families of graphs. Many of the families for which crossing numbers have been determined correspond to cartesian products of two graphs. Here, the cartesian product of the sunlet graph, denoted ${\mathcal{S}}_{n}$, and the star graph, denoted $K_{1,m}$, is considered for the first time. It is proved that the crossing number of ${\mathcal{S}}_{n}\Box K_{1,2}$ is $n$, and the crossing number of ${\mathcal{S}}_{n}\Box K_{1,3}$ is $3n$. An upper bound for the crossing number of ${\mathcal{S}}_{n}\Box K_{1,m}$ is also given.

Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r=ω(√logn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on dE(u, v) conditional on dE(u, v).

A property of finite graphs is called non-deterministically testable if it has a ‘certificate’ such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or more unary and/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that non-deterministically testable properties are also deterministically testable.

Let Dn.m, be the diameter of a connected undirected graph on n ≥2 vertices and n - 1 ≤ m ≤ s(n) edges, where s(n) = n(n — l)/2. Then Dn.s(n) = 1, and for ms(n) it is shown that

The bounds on Dn.m, are sharp.