The crossing numbers of Cartesian products of paths with 5-vertex graphs

被引：30
|
作者：
Klesc, M [1 ]
机构：
[1] Tech Univ, Fac Elect Engn & Informat, Dept Math, Kosice 04200, Slovakia
来源：
DISCRETE MATHEMATICS | 2001年 / 233卷 / 1-3期
关键词：
graph; drawing; crossing number; path; Cartesian product;
D O I：
10.1016/S0012-365X(00)00251-X
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
For two graphs defined from K-5 by removing one edge or two nonadjacent edges we prove that the crossing number of Cartesian product of the graph with the path of length n is 4n and 3n-1, respectively These results complete the crossing numbers list of Cartesian products of ail 5-vertex graphs with paths. We also give a description of Cartesian products of 5-vertex graphs with cycles and stars, whose crossing numbers are known. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：353 / 359
页数：7
相关论文
共 50 条
  • [21] Vertex-neighbor-toughness of the Cartesian Products of paths and cycles
    Wei, Zongtian
    Yang, Jingting
    Li, Yinkui
    Yue, Chao
    ARS COMBINATORIA, 2019, 147 : 63 - 78
  • [22] The crossing number of Cartesian products of complete bipartite graphs K2,m with paths Pn
    Ling, Tang
    Shengxiang, Lv
    Yuanqiu, Huang
    GRAPHS AND COMBINATORICS, 2007, 23 (06) : 659 - 666
  • [23] The Crossing Number of Cartesian Products of Complete Bipartite Graphs K2,m with Paths Pn
    Tang Ling
    Lv Shengxiang
    Huang Yuanqiu
    Graphs and Combinatorics, 2007, 23 : 659 - 666
  • [24] On the δ-chromatic numbers of the Cartesian products of graphs
    Tangjai, Wipawee
    Pho-on, Witsarut
    Vichitkunakorn, Panupong
    OPEN MATHEMATICS, 2024, 22 (01):
  • [25] On the crossing numbers of the join products of five graphs on six vertices with discrete graphs
    Berezny, Stefan
    Stas, Michal
    CARPATHIAN JOURNAL OF MATHEMATICS, 2023, 39 (02) : 371 - 382
  • [26] Crossing numbers of Cartesian product of path with certain graphs on six vertices
    Gayathri, S.
    Bharati, R.
    Stas, M.
    Petrillova, J.
    UTILITAS MATHEMATICA, 2020, 116 : 13 - 20
  • [27] Crossing Numbers of Join Product with Discrete Graphs: A Study on 6-Vertex Graphs
    Fortes, Jana
    Stas, Michal
    MATHEMATICS, 2023, 11 (13)
  • [28] The secure domination number of Cartesian products of small graphs with paths and cycles
    Haythorpe, Michael
    Newcombe, Alex
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 32 - 45
  • [29] On the Crossing Numbers of Join Products of Four Graphs of Order Six With the Discrete Graph
    Stas, M.
    AZERBAIJAN JOURNAL OF MATHEMATICS, 2022, 12 (01): : 80 - 97
  • [30] ON THE CROSSING NUMBERS OF JOIN PRODUCTS OF FIVE GRAPHS OF ORDER SIX WITH THE DISCRETE GRAPH
    Stas, Michal
    OPUSCULA MATHEMATICA, 2020, 40 (03) : 383 - 397
12345