The Crossing Numbers of Products of Path with Graphs of Order Six
The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartes...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
University of Zielona Góra
2013-07-01
|
Series: | Discussiones Mathematicae Graph Theory |
Subjects: | |
Online Access: | https://doi.org/10.7151/dmgt.1684 |
_version_ | 1797757785699516416 |
---|---|
author | Klešč Marián Petrillová Jana |
author_facet | Klešč Marián Petrillová Jana |
author_sort | Klešč Marián |
collection | DOAJ |
description | The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collected |
first_indexed | 2024-03-12T18:20:31Z |
format | Article |
id | doaj.art-c40f04257237470b80796d5c531089c7 |
institution | Directory Open Access Journal |
issn | 2083-5892 |
language | English |
last_indexed | 2024-03-12T18:20:31Z |
publishDate | 2013-07-01 |
publisher | University of Zielona Góra |
record_format | Article |
series | Discussiones Mathematicae Graph Theory |
spelling | doaj.art-c40f04257237470b80796d5c531089c72023-08-02T08:58:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-07-0133357158210.7151/dmgt.1684The Crossing Numbers of Products of Path with Graphs of Order SixKlešč Marián0Petrillová Jana1Faculty of Electrical Engineering and Informatics Technical University of Košice Letná 9, 042 00 Košice, Slovak RepublicFaculty of Electrical Engineering and Informatics Technical University of Košice Letná 9, 042 00 Košice, Slovak RepublicThe crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the Cartesian product H⃞Pn is 2(n − 1). In addition, the crossing numbers of G⃞Pn for fourty graphs G on six vertices are collectedhttps://doi.org/10.7151/dmgt.1684graphdrawingcrossing numbercartesian productpathtree |
spellingShingle | Klešč Marián Petrillová Jana The Crossing Numbers of Products of Path with Graphs of Order Six Discussiones Mathematicae Graph Theory graph drawing crossing number cartesian product path tree |
title | The Crossing Numbers of Products of Path with Graphs of Order Six |
title_full | The Crossing Numbers of Products of Path with Graphs of Order Six |
title_fullStr | The Crossing Numbers of Products of Path with Graphs of Order Six |
title_full_unstemmed | The Crossing Numbers of Products of Path with Graphs of Order Six |
title_short | The Crossing Numbers of Products of Path with Graphs of Order Six |
title_sort | crossing numbers of products of path with graphs of order six |
topic | graph drawing crossing number cartesian product path tree |
url | https://doi.org/10.7151/dmgt.1684 |
work_keys_str_mv | AT klescmarian thecrossingnumbersofproductsofpathwithgraphsofordersix AT petrillovajana thecrossingnumbersofproductsofpathwithgraphsofordersix AT klescmarian crossingnumbersofproductsofpathwithgraphsofordersix AT petrillovajana crossingnumbersofproductsofpathwithgraphsofordersix |