Calculating Crossing Numbers of Graphs Using Their Redrawings
The main aim of the paper is to give the crossing number of the join product <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>G</mi><mo>*</mo></msup><mo>+...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-01-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/15/1/175 |
| _version_ | 1797436847546171392 |
|---|---|
| author | Michal Staš |
| author_facet | Michal Staš |
| author_sort | Michal Staš |
| collection | DOAJ |
| description | The main aim of the paper is to give the crossing number of the join product <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>G</mi><mo>*</mo></msup><mo>+</mo><msub><mi>D</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. The connected graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mo>*</mo></msup></semantics></math></inline-formula> of order six is isomorphic to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>K</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>\</mo><mi>e</mi></mrow></semantics></math></inline-formula> obtained by removing one edge from the complete bipartite graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub></semantics></math></inline-formula>, and the discrete graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>n</mi></msub></semantics></math></inline-formula> consists of <i>n</i> isolated vertices. The proofs were carried out with the help of several possible redrawings of the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mo>*</mo></msup></semantics></math></inline-formula> with respect to its many symmetries. |
| first_indexed | 2024-03-09T11:08:30Z |
| format | Article |
| id | doaj.art-d1ebc2debb824465a260e9b712db70b7 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-09T11:08:30Z |
| publishDate | 2023-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-d1ebc2debb824465a260e9b712db70b72023-12-01T00:53:00ZengMDPI AGSymmetry2073-89942023-01-0115117510.3390/sym15010175Calculating Crossing Numbers of Graphs Using Their RedrawingsMichal Staš0Faculty of Electrical Engineering and Informatics, Technical University of Košice, 042 00 Košice, SlovakiaThe main aim of the paper is to give the crossing number of the join product <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>G</mi><mo>*</mo></msup><mo>+</mo><msub><mi>D</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. The connected graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mo>*</mo></msup></semantics></math></inline-formula> of order six is isomorphic to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>K</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>\</mo><mi>e</mi></mrow></semantics></math></inline-formula> obtained by removing one edge from the complete bipartite graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub></semantics></math></inline-formula>, and the discrete graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>n</mi></msub></semantics></math></inline-formula> consists of <i>n</i> isolated vertices. The proofs were carried out with the help of several possible redrawings of the graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>G</mi><mo>*</mo></msup></semantics></math></inline-formula> with respect to its many symmetries.https://www.mdpi.com/2073-8994/15/1/175graphoptimal drawingcrossing numberjoin productrotationredrawing |
| spellingShingle | Michal Staš Calculating Crossing Numbers of Graphs Using Their Redrawings Symmetry graph optimal drawing crossing number join product rotation redrawing |
| title | Calculating Crossing Numbers of Graphs Using Their Redrawings |
| title_full | Calculating Crossing Numbers of Graphs Using Their Redrawings |
| title_fullStr | Calculating Crossing Numbers of Graphs Using Their Redrawings |
| title_full_unstemmed | Calculating Crossing Numbers of Graphs Using Their Redrawings |
| title_short | Calculating Crossing Numbers of Graphs Using Their Redrawings |
| title_sort | calculating crossing numbers of graphs using their redrawings |
| topic | graph optimal drawing crossing number join product rotation redrawing |
| url | https://www.mdpi.com/2073-8994/15/1/175 |
| work_keys_str_mv | AT michalstas calculatingcrossingnumbersofgraphsusingtheirredrawings |