A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929495976443904 |
|---|---|
| author | Asiri, Zayed Burdett, Ryan Chimani, Markus Haythorpe, Michael Newcombe, Alex Wagner, Mirko H. |
| author_facet | Asiri, Zayed Burdett, Ryan Chimani, Markus Haythorpe, Michael Newcombe, Alex Wagner, Mirko H. |
| contents | Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the establishment of coincident upper and lower bounds; the former is usually demonstrated by providing a suitable drawing procedure, while the latter often requires substantial theoretical arguments. Many such papers have been published, which typically focus on just one or two small graphs at a time, and use ad hoc arguments specific to those graphs. We propose a general approach which, when successful, establishes the required lower bound. This approach can be applied to the Cartesian product of any graph with arbitrarily large paths, and in each case involves solving a modified version of the crossing number problem on a finite number (typically only two or three) of small graphs. We demonstrate the potency of this approach by applying it to Cartesian products involving all 133 graphs $G$ of orders five or six, and show that it is successful in 128 cases. This includes 60 cases which a recent survey listed as either undetermined, or determined only in journals without adequate peer review. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06755 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Systematic Approach to Crossing Numbers of Cartesian Products with Paths Asiri, Zayed Burdett, Ryan Chimani, Markus Haythorpe, Michael Newcombe, Alex Wagner, Mirko H. Combinatorics Discrete Mathematics 05C62, 68R10 G.2.2 Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the establishment of coincident upper and lower bounds; the former is usually demonstrated by providing a suitable drawing procedure, while the latter often requires substantial theoretical arguments. Many such papers have been published, which typically focus on just one or two small graphs at a time, and use ad hoc arguments specific to those graphs. We propose a general approach which, when successful, establishes the required lower bound. This approach can be applied to the Cartesian product of any graph with arbitrarily large paths, and in each case involves solving a modified version of the crossing number problem on a finite number (typically only two or three) of small graphs. We demonstrate the potency of this approach by applying it to Cartesian products involving all 133 graphs $G$ of orders five or six, and show that it is successful in 128 cases. This includes 60 cases which a recent survey listed as either undetermined, or determined only in journals without adequate peer review. |
| title | A Systematic Approach to Crossing Numbers of Cartesian Products with Paths |
| topic | Combinatorics Discrete Mathematics 05C62, 68R10 G.2.2 |
| url | https://arxiv.org/abs/2409.06755 |