The crossing numbers of join products of four graphs of order five with paths and cycles
The crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join pr...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
AGH Univeristy of Science and Technology Press
2023-07-01
|
Series: | Opuscula Mathematica |
Subjects: | |
Online Access: | https://www.opuscula.agh.edu.pl/vol43/6/art/opuscula_math_4342.pdf |
_version_ | 1797774664503656448 |
---|---|
author | Michal Staš Mária Timková |
author_facet | Michal Staš Mária Timková |
author_sort | Michal Staš |
collection | DOAJ |
description | The crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products \(G^\ast + P_n\) and \(G^\ast + C_n\) for the disconnected graph \(G^\ast\) consisting of the complete tripartite graph \(K_{1,1,2}\) and one isolated vertex are given, where \(P_n\) and \(C_n\) are the path and the cycle on \(n\) vertices, respectively. In the paper also the crossing numbers of \(H^\ast + P_n\) and \(H^\ast + C_n\) are determined, where \(H^\ast\) is isomorphic to the complete tripartite graph \(K_{1,1,3}\). Finally, by adding new edges to the graphs \(G^\ast\) and \(H^\ast\), we are able to obtain crossing numbers of join products of two other graphs \(G_1\) and \(H_1\) with paths and cycles. |
first_indexed | 2024-03-12T22:24:24Z |
format | Article |
id | doaj.art-258c4dad4745482287c531790b8bf07d |
institution | Directory Open Access Journal |
issn | 1232-9274 |
language | English |
last_indexed | 2024-03-12T22:24:24Z |
publishDate | 2023-07-01 |
publisher | AGH Univeristy of Science and Technology Press |
record_format | Article |
series | Opuscula Mathematica |
spelling | doaj.art-258c4dad4745482287c531790b8bf07d2023-07-22T07:15:50ZengAGH Univeristy of Science and Technology PressOpuscula Mathematica1232-92742023-07-01436865883https://doi.org/10.7494/OpMath.2023.43.6.8654342The crossing numbers of join products of four graphs of order five with paths and cyclesMichal Staš0https://orcid.org/0000-0002-2837-8879Mária Timková1https://orcid.org/0000-0001-5499-9399Technical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics, 042-00 Košice, Slovak RepublicTechnical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics, 042-00 Košice, Slovak RepublicThe crossing number \(\mathrm{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products \(G^\ast + P_n\) and \(G^\ast + C_n\) for the disconnected graph \(G^\ast\) consisting of the complete tripartite graph \(K_{1,1,2}\) and one isolated vertex are given, where \(P_n\) and \(C_n\) are the path and the cycle on \(n\) vertices, respectively. In the paper also the crossing numbers of \(H^\ast + P_n\) and \(H^\ast + C_n\) are determined, where \(H^\ast\) is isomorphic to the complete tripartite graph \(K_{1,1,3}\). Finally, by adding new edges to the graphs \(G^\ast\) and \(H^\ast\), we are able to obtain crossing numbers of join products of two other graphs \(G_1\) and \(H_1\) with paths and cycles.https://www.opuscula.agh.edu.pl/vol43/6/art/opuscula_math_4342.pdfgraphcrossing numberjoin productpathcycleseparating cycle |
spellingShingle | Michal Staš Mária Timková The crossing numbers of join products of four graphs of order five with paths and cycles Opuscula Mathematica graph crossing number join product path cycle separating cycle |
title | The crossing numbers of join products of four graphs of order five with paths and cycles |
title_full | The crossing numbers of join products of four graphs of order five with paths and cycles |
title_fullStr | The crossing numbers of join products of four graphs of order five with paths and cycles |
title_full_unstemmed | The crossing numbers of join products of four graphs of order five with paths and cycles |
title_short | The crossing numbers of join products of four graphs of order five with paths and cycles |
title_sort | crossing numbers of join products of four graphs of order five with paths and cycles |
topic | graph crossing number join product path cycle separating cycle |
url | https://www.opuscula.agh.edu.pl/vol43/6/art/opuscula_math_4342.pdf |
work_keys_str_mv | AT michalstas thecrossingnumbersofjoinproductsoffourgraphsoforderfivewithpathsandcycles AT mariatimkova thecrossingnumbersofjoinproductsoffourgraphsoforderfivewithpathsandcycles AT michalstas crossingnumbersofjoinproductsoffourgraphsoforderfivewithpathsandcycles AT mariatimkova crossingnumbersofjoinproductsoffourgraphsoforderfivewithpathsandcycles |