Exploring the Crossing Numbers of Three Join Products of 6-Vertex Graphs with Discrete Graphs

Abstract

The significance of searching for edge crossings in graph theory lies inter alia in enhancing the clarity and readability of graph representations, which is essential for various applications such as network visualization, circuit design, and data representation. This paper focuses on exploring the crossing number of the join product G*+Dn, where G* is a graph isomorphic to the path on four vertices P4 with an additional two vertices adjacent to two inner vertices of P4, and Dn is a discrete graph composed of n isolated vertices. The proof is based on exact crossing-number values for join products involving particular subgraphs Hk of G* with discrete graphs Dn combined with the symmetrical properties of graphs. This approach could also be adapted to determine the unknown crossing numbers of two other 6-vertices graphs obtained by adding one or two additional edges to the graph G*.

Keywords

• crossing number
• discrete graphs
• good drawing
• join product
• paths
• redrawing