On the Crossing Number of the Cartesian Product of a Sunlet Graph and a Star Graph
Michael Haythorpe Alex Newcombe


Crossing number of cartesian product of Sunlet and Star graphs




1]Michael Haythorpe
[1]1284 South Road, Clovelly Park, 5042

College of Science and Engineering

Flinders University, Australiamichael.haythorpe@flinders.edu.au

2]Alex Newcombe
[2]1284 South Road, Clovelly Park, 5042

College of Science and Engineering

Flinders University, Australiaalex.newcombe@flinders.edu.au

M. Haythorpe and A. Newcombe

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 𝒮_n, and the Star graph, denoted K_1,m, is considered for the first time. It is proved that the crossing number of 𝒮_n  K_1,2 is n, and the crossing number of 𝒮_n  K_1,3 is 3n. An upper bound for the crossing number of 𝒮_n  K_1,m is also given.

primary 05C10; secondary 68R10



On the crossing number of the cartesian product of a Sunlet graph and a Star graph
    [
    December 30, 2023
==================================================================================





§ INTRODUCTION


Consider a simple graph G with vertex set V(G) and edge set E(G). A drawing is an embedding of the graph in the plane, in the sense that each vertex v ∈ V(G) is assigned coordinates in the plane, and each edge e ∈ E(G) is drawn as a curve starting and ending at the coordinates of its endpoints. A good drawing is one in which edges have at most one point in common, no more than two edges cross at a single point, and edges which share an endpoint do not cross. For a given drawing D of the graph G, the crossings in the drawing, denoted cr_D(G) can then be computed as the number of times two edges intersect at points other than at their endpoints. The crossing number cr(G) of a graph G is the smallest number of crossings over all possible drawings of G. It is well known that any drawing of G which contains cr(G) crossings is a good drawing.

The crossing number problem, being the problem of determining the crossing number of a graph, is known to be NP-hard <cit.>; this is true even for graphs constructed by adding a single edge to a planar graph <cit.>. Indeed, the crossing number problem is known to be notoriously difficult, and is still unsolved even for very small instances. For example, the crossing number of K_13 has still not been determined, although it is known to be either 223 or 225 <cit.>. However, the crossing number has been determined for some infinite families of graphs. In many such cases, the family is created by taking the cartesian product of members of two smaller graph families. To the best of the authors' knowledge, the first such result published was due to Harary et al <cit.> in 1973, who conjectured that the crossing number of C_m  C_n, that is, the cartesian product of two arbitrarily large cycles, would be (m-2)n for n ≥ m ≥ 3. To date, this conjecture remains unproven, although a number of partial results have been determined. Specifically, the conjecture is known to be true for m ≤ 7, and also whenever n ≥ m(m-1) <cit.>. Other infinite graph families, for which the crossing number of their cartesian products have been studied, include Paths and Stars <cit.>, Complete graphs and Cycles <cit.>, Cycles and Stars <cit.>, Wheels and Trees <cit.>, and Cycles with the 2-power of Paths <cit.>.

In the present work, we expand this growing literature by considering the cartesian product of a Sunlet graph and a Star graph. The Sunlet graph on 2n vertices, denoted 𝒮_n for n ≥ 3, is constructed by attaching n pendant edges to an n-cycle C_n; see Figure <ref> for an example of 𝒮_6. The Star graph on m+1 vertices consists of one vertex of degree m attached to m vertices of degree 1. It is usually denoted S_m, however to avoid confusion with the notation for the Sunlet graph, we note that the Star graph is equivalent to the complete bipartite graph K_1,m, and use that notation instead. We will show that cr(𝒮_n  K_1,m) ≤ nm(m-1)/2 for n ≥ 3 and m ≥ 1. We will also prove that the crossing number meets this bound precisely for m = {1, 2, 3}, and conjecture that it does so for all m ∈ℤ+.





§ UPPER BOUND


We begin by providing an upper bound for cr(𝒮_n  K_1,m). In what follows, let the vertex labels of K_1,m be v_0 for the vertex of degree m and v_1, v_2, , v_m for the vertices of degree 1. Let the vertex labels of 𝒮_n be u_0, u_1, u_2, , u_n-1 for the vertices on the cycle and let u_i' denote the pendant vertex attached to u_i.

The crossing number of 𝒮_n  K_1,m is no larger than nm(m-1)/2 for n ≥ 3, m ≥ 1.

It is easy to check that 𝒮_n  K_1,1 is planar; for instance, a planar drawing of 𝒮_6  K_1,1 is illustrated in Figure <ref>, which can obviously be extended for any n. It then suffices to give a procedure for drawing the graph 𝒮_n  K_1,m, m ≥ 2, so that the number of crossings meets the proposed upper bound.



First, note that 𝒮_n  K_1,m contains C_n  K_1,m as a subgraph. Begin by drawing the subgraph C_n  K_1,m in the manner illustrated in Figure <ref>(a). For a given i = 0, 1, , n-1, the thick edges represent ((v_0,u_i),(v_j,u_i)) for j = 0, 1, , m. The dashed edges represent ((v_j,u_i),(v_j,u_i+1)) and ((v_j,u_i),(v_j,u_i-1)) for j = 0, 1, , m. Then, it is easy to see that the dashed edges can be joined to the corresponding sections for i+1 and i-1 to complete a drawing of K_1,m C_n without introducing any additional crossings. Hence, the number of crossings in this drawing of the subgraph C_n  K_1,m is:


    n( ∑_k=1^⌊m/2⌋-1 k + ∑_k=1^⌈m/2⌉ -1 k ) = n⌊m/2⌋⌊m-1/2⌋.




Next, we extend this drawing to a drawing of 𝒮_n  K_1,m in the following way. For each i = 0, 1, , n-1, place a vertex in the region between the centre horizontal (dashed) edge ((v_0,u_i),(v_0,u_i+1)) and the first thick edge on the side which possesses ⌈ m/2 ⌉ vertices, and join this new vertex to each of the vertices (v_j, u_i) for j = 0, 1, , m as in Figure <ref>(b). Then, the number of crossings in this graph is equal to:


    n(⌊m/2⌋⌊m-1/2⌋ + ∑_k=1^⌊m/2⌋ k + ∑_k=1^⌈m/2⌉ -1 k )
    
    =n ⌊m/2⌋( ⌊m-1/2⌋ + ⌈m/2⌉) 
    
    =n m(m-1)/2.


Finally, if every new edge is subdivided, except for the ones emanating from (v_0,u_i) for i = 0, 1, , n-1, the resulting graph is isomorphic to 𝒮_n  K_1,m. Since subdividing edges does not alter the number of crossings, we conclude that it is possible to draw 𝒮_n  K_1,m with nm(m-1)/2 crossings.




§ EXACT RESULTS


We now consider 𝒮_n  K_1,m for some small values of m, and show that the crossing number coincides precisely with the upper bound from Section <ref>. Denote that upper bound by U(n,m) := nm(m-1)/2. As noted previously, 𝒮_n  K_1,1 is planar; see Figure <ref>. This agrees with U(n,1) = 0. Next, we will consider the cases when m = 2 and m = 3.

In what follows, we will utilise some properties of subgraphs of 𝒮_n  K_1,m, which we denote by H_i for each i = 0,1,2,,n-1. In particular, H_i is defined as the subgraph induced by the union of the following, disjoint, sets of edges:



   a_i := {((v_j,u_i),(v_j,u_i+1)) | j=0,1,…,m}

   b_i := {((v_j,u_i),(v_j,u'_i)) | j=0,1,…,m}

   b'_i := {((v_0,u'_i),(v_j,u'_i)) | j=1,…,m}

   c_i := {((v_j,u_i),(v_j,u_i-1)) | j=0,1,…,m}

   t_i := {((v_0,u_i),(v_j,u_i)) | j=1,…,m}

   t_i+1 := {((v_0,u_i+1),(v_j,u_i+1)) | j=1,…,m}

   t_i-1 := {((v_0,u_i-1),(v_j,u_i-1)) | j=1,…,m}

A detailed illustration of H_i, for the case m=3, is displayed in Figure <ref>.  For each i=0,1,2,…,n-1, there is a corresponding H_i in 𝒮_n  K_1,m and H_i and H_j contain common edges when j=i+1 or j=i-1.



We now consider the case when m = 2. Note that U(n,2) = n. In what follows, we use the following notation: consider a drawing D of a graph which contains two edge sets a and b.  Then cr_D(a) is equal to the number of crossings on the edges of a in D.  Similarly, cr_D(a,b) is equal to the number of crossings in D between edge-pairs, such that one edge is contained in a and the other is contained in b.

The crossing number of 𝒮_n  K_1,2 is equal to n.

From Theorem <ref>, we know that cr(𝒮_n  K_1,2) ≤ n. Hence, the task now is to show that the reverse inequality holds. Let H'_i be the subgraph H_i without the edges t_i. An illustration of H'_i is displayed in Figure <ref>.



It is clear that H'_i is homeomorphic to K_3,3, and so there exists at least one crossing in the subdrawing D' of H'_i. Furthermore, at least one crossing in D' involves two edges which come from the edge sets (a_i ∪ t_i+1), (b_i ∪ b'_i) and (c_i ∪ t_i-i), but do not both come from the same edge set. That is,


    cr_D'((a_i ∪ t_i+1),(b_i ∪ b'_i)) + cr_D'((a_i ∪ t_i+1),(c_i ∪ t_i-1)) + cr_D'((b_i ∪ b'_i),(c_i ∪ t_i+1)) ≥ 1.


Hence, it is clear that there is at least one crossing in each H'_i which does not occur in any other H'_j for i ≠ j, which leads immediately to the result.

Next, we consider the case when m = 3. Note that U(n,3) = 3n. In order to handle this case, we first need to prove two intermediate results, Lemmas <ref>–<ref>.



For m = 3, consider the following four edge sets: (a_i ∪ t_i+1), (b_i ∪ b'_i), (c_i ∪ t_i-1) and t_i. Then, in any good drawing of the subgraph H_i, there are at least 3 crossings for which the two edges involved in the crossing are not in the same set.



H_i is homeomorphic to K_1,3,3, and Asano <cit.> proved that cr(K_1,3,3)=3.  Any drawing of H_i corresponds to some drawing of K_1,3,3.  Any drawing of K_1,3,3 has at least three crossings between pairs of edges which are not incident.  These crossings correspond precisely to crossings in the drawing of H_i which satisfy the Lemma.


For n ≥ 3, let D be a drawing of 𝒮_n  K_1,3. If, for each i = 0, 1, 2, , n-1, the edges t_i ∪ b_i ∪ b'_i are crossed two or fewer times in D, then D has at least 3n crossings.







































Let F_i denote the edge set t_i ∪ b_i ∪ b'_i. Note that F_i is a subgraph of H_i. Then, from Lemma <ref>, we have

    cr_D(a_i ∪ t_i+1,F_i)+cr_D(c_i ∪ t_i-1,F_i)+cr_D((a_i∪ t_i+1),(c_i ∪ t_i-1))+cr_D(F_i ,F_i) ≥ 3.


Assume that cr_D(F_i) ≤ 2 for all i = 0,1,2,,n-1.  It will be shown that if cr_D(t_i+1,F_i) ≠ 0, or if cr_D(t_i-1,F_i) ≠ 0, then a contradiction arises.

Suppose that cr_D(t_i+1,F_i) = 1.  Note that the edges of b_i+1 link to all of the endpoints of t_i+1.  Since the subgraph induced by F_i is 2-connected, it is clear that it is impossible to draw (b_i+1∪ b'_i+1) without creating an additional crossing on the edges of F_i.  Since the subgraph induced by F_i ∪ c_i ∪ t_i-1 is isomorphic to P_2  K_1,3, where P_2 denotes the path graph on 3 vertices, and cr(P_2  K_1,3)=1 <cit.>, the following also holds


    cr_D(c_i ∪ t_i-1,F_i)+cr_D(F_i,F_i) ≥ 1.


This would imply that F_i is crossed at least three times, but by assumption, cr_D(F_i) ≤ 2. Hence, cr_D(t_i+1,F_i) ≠ 1. An analogous argument can be made for t_i-1 which, similarly, implies that cr_D(t_i-1,F_i) ≠ 1 as well.

Suppose that cr_D(t_i+1,F_i) = 2. Then, since cr_D(F_i) ≤ 2, it must be the case that cr_D(F_i,F_i) = 0, and hence without loss of generality, the subdrawing of the subgraph induced by F_i is equivalent to the drawing displayed in Figure <ref>.



Now consider the rest of the subgraph H_i, which includes edge sets (a_i ∪ t_i+1) and (c_i ∪ t_i-1). Note that the edges c_i link to all of the endpoints of t_i, and these do not lie on a common face of D, so (c_i ∪ t_i-1) cannot be drawn without crossing F_i at least once. This would imply that F_i is crossed at least three times, but by assumption, cr_D(F_i) ≤ 2.  Hence, cr_D(t_i+1,F_i) ≠ 2. An analogous argument can be made for t_i-1 which, similarly, implies that cr_D(t_i-1,F_i) ≠ 2 as well.

Then, since cr_D(F_i) ≤ 2, the only remaining possibility is that cr_D(t_i+1,F_i) = cr_D(t_i-1,F_i) = 0, and so (<ref>) simplifies to


    cr_D(a_i,F_i)+cr_D(c_i,F_i)+cr_D((a_i∪ t_i+1),(c_i ∪ t_i-1))+cr_D(F_i,F_i) ≥ 3.


It can be easily seen that any crossing counted by the left hand side of (<ref>) is not counted for any other j ≠ i.  Hence summing (<ref>) over i=0,1,2,…,n-1 provides the result.


Finally, we are ready to propose the theorem for m = 3.

For n ≥ 3, the crossing number of 𝒮_n  K_1,3 is equal to 3n.

We will prove the result by induction. The base case where n = 3, corresponding to a graph on 24 vertices, was proved computationally, utilising the exact crossing minimisation methods of Chimani and Wiedera <cit.>, which are available at http://crossings.uos.de. The proof comes from a solution to an appropriately constructed integer linear program and shows that cr(𝒮_3  K_1,3) = 9. The proof file is available and can be provided by the corresponding author if desired.

Now, assume that cr(𝒮_n  K_1,3) = 3n for each n = 3, , k-1, but that for n = k there exists a drawing with strictly fewer than 3k crossings. Let D denote such a drawing. By Lemma <ref>, there must be at least one i such that the edges of F_i are crossed at least three times in D. Hence, the edges F_i could be deleted and the number of crossings remaining would be strictly less than 3(k-1). However, once F_i is deleted, the resulting graph is homeomorphic to 𝒮_k-1 K_1,3, which by the inductive assumption has crossing number equal to 3(k-1). This is a contradiction, and hence any drawing for n=k must have at least 3k crossings.  This, combined with Theorem <ref> implies that cr(𝒮_k  K_1,3) = 3k, and inductively we obtain the result. 

We conclude by conjecturing that the upper bound described in Theorem <ref> coincides precisely with the crossing number in all cases. To provide evidence supporting this conjecture, we used QuickCross <cit.>, a recently developed crossing minimization heuristic, to find good drawings of 𝒮_n  K_1,m for n,m ≤ 20. In all cases, QuickCross was able to find an embedding that agrees with the conjecture but was never able to find an embedding with fewer crossings.

For n ≥ 3, m ≥ 1,

    cr(𝒮_n  K_1,m) = nm(m-1)/2





99
abrego Ábrego, B.M., Aichholzer, O., Fernández-Merchant, S., Hackl, T., Pammer, J., Pilz, A., Ramos, P., Salazar, G., Vogtenhuber, B.  All Good Drawings of Small Complete Graphs.  In: Proc. 31st European Workshop on Computational Geometry (EuroCG), pp. 57–60, 2015.
anderson Anderson, M., Richter, R.B., Rodney, P.  The Crossing Number of C6 × C6.  Congressus Numerantium, 117:97–107, 1996.
anderson2 Anderson, M., Richter, R.B., Rodney, P.  The Crossing Number of C7 × C7.  Congressus Numerantium, 125:97–117, 1996.
asano Asano, K.  The crossing number of K_1,3,n and K_2,3,n. J. Graph Th., 10:1–8, 1986.
beinekeBeineke, L.W. and Ringeisen, R.D.  On the crossing numbers of products of cycles and graphs of order four.  J. Graph Th., 4(2):145–155, 1980.
bokal Bokal, D.  On the crossing number of Cartesian products with paths.  J. Comb. Th. Series B, 97(3):381–384, 2007.
cabello Cabello, S. and Mohar, B.  Adding one edge to Planar graphs makes Crossing Number and 1-Planarity hard.  SIAM J. Comput., 42(5):1803–1829, 2013.
chimani Chimani, M. and Wiedera, T.  An ILP-based Proof System for the Crossing Number Problem. In: 24th European Symposium of Algorithms (ESA) 2016, Aarhus, Denmark, Leibniz. Int. Prov. Inform. 56:29.1–29.13, 2016.
quickcross Clancy, K., Haythorpe, M. and Newcombe, A.  An effective crossing minimisation heuristic based on star insertion", J. Graph Alg. App., submitted 2018. Available at: http://arxiv.org/abs/1804.09900
deanrichter Dean, A.M. and Richter, R.B.  The crossing number of C4 × C4. J. Graph Th., 19(1):125–129, 1995.
gareyjohnson Garey, M.R. and Johnson, D.S.  Crossing number is NP-complete.  SIAM J. Algebraic Disc. Meth., 4(3):312–316, 1983.
glebsky Glebsky, L.Y. and Salazar, Gelasio.  The crossing number of Cm × Cn is as conjectured for n ≥ m(m+1).  J. Graph Th., 47(1):53–72, 2004.
harary Harary, F., Kainen, P.C., Schwenk, A.J.  Toroidal graphs with arbitrarily high crossing numbers.  Nanta. Math., 6(1):58–67, 1973.
jendrolscerbova Jendrol, S. and Šcerbová, M.  On the crossing numbers of Sm × Pn and Sm × Cn. Casopis pro pestováni matematiky, 107:225–230, 1982.
klesc1991 Klešč, M.  On the crossing numbers of Cartesian products of stars and paths or cycles.  Math. Slovaca, 41(2):113–120, 1991.
klesc2012 Klešč, M. and Kravecová, D.  The crossing number of P^2_n  C_3.  Disc. Math., 312:2096–2101, 2012.
klesc2017 Klešč, M., Petrillová, J., Valo, M.  On the crossing numbers of cartesian products of wheels and trees.  Disc. Math. Graph Th., 37(2):399-413, 2017.
mcquillan McQuillan, D., Pan, S., Richter, R.B.  On the crossing number of K_13.  J. Combin. Th. Series B, 115:224–235, 2015.
richterthomassen Richter, R.B. and Thomassen, C.  Intersections of curve systems and the crossing number of C5 × C5. Disc. Comput. Geom., 13(1):149–159, 1995.
ringeisen Ringeisen, R.D. and Beineke, L.W.  The crossing number of C_3 × C_n.  J. Combin. Th. Series B, 24(2):134–136, 1978.
wenping Zheng, W., Lin, X. Yang, Y., Deng, C.  On the crossing number of K_m  C_n and K_m,l P_n.  Disc. Appl. Math., 156:1892–1907, 2008.








