On the Crossing Number of the Cartesian Product of a Sunlet Graph and a Star Graph

2019/02/27 by Haythorpe, Michael, Newcombe, Alex
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.10357

Abstract

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

Related

• On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars
• A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
• A survey of graphs with known or bounded crossing numbers
• The crossing numbers of K_m× P_n and K_m× C_n
• The crossing numbers of K_n,n-nK₂, K_n× P₂, K_n× P₃ and K_n× C₄