The Crossing Numbers of Join of Special Disconnected Graph on Five Vertices with Discrete Graphs

被引：9
作者：
Klesc, Marian [1 ]
Stas, Michal [1 ]
Petrillova, Jana [1 ]
机构：
[1] Tech Univ Kosice, Fac Elect Engn & Informat, Kosice, Slovakia
来源：
GRAPHS AND COMBINATORICS | 2022年 / 38卷 / 02期
关键词：
Graph; Drawing; Crossing number; Join product; Vertex rotation; CYCLIC PERMUTATIONS; PRODUCTS;
D O I：
10.1007/s00373-021-02423-5
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In the paper, the crossing number of the join product G* + D-n for the disconnected graph G* consisting of one isolated vertex and of one component isomorphic to K-1,K-1,K-2 is given. Moreover, the crossing numbers of H-i + D-n for three other graphs H-i of order five are also established. These results extend a small number of known results concerning crossing numbers of join products. The methods used in the paper are new. They are based on combinatorial properties of cyclic permutations.
引用
收藏
页数：19
相关论文
共 16 条
  • [1] Berezny S, 2019, CARPATHIAN J MATH, V35, P137
  • [2] Berezny S, 2018, CARPATHIAN J MATH, V34, P143
  • [3] A branch-and-cut approach to the crossing number problem
    Buchheim, Christoph
    Chimani, Markus
    Ebner, Dietmar
    Gutwenger, Carsten
    Juenger, Michael
    Klau, Gunnar W.
    Mutzel, Petra
    Weiskircher, Rene
    [J]. DISCRETE OPTIMIZATION, 2008, 5 (02) : 373 - 388
  • [4] Chimani M., 2009, ACM J EXP ALGORITHM, V14
  • [5] Chimani M, 2008, LECT NOTES COMPUT SC, V5193, P284, DOI 10.1007/978-3-540-87744-8_24
  • [6] CROSSING NUMBER IS NP-COMPLETE
    GAREY, MR
    JOHNSON, DS
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03): : 312 - 316
  • [7] Hernández-Vélez C, 2014, ELECTRON J COMB, V21
  • [8] Kleitman D. J., 1970, Journal of Combinatorial Theory, Series A, V9, P315, DOI 10.1016/S0021-9800(70)80087-4
  • [9] Klesc Marian, 2012, Mathematical Modeling and Computational Science. International Conference, MMCP 2011. Revised Selected Papers, P160, DOI 10.1007/978-3-642-28212-6_15
  • [10] The crossing numbers of Cartesian products of paths with 5-vertex graphs
    Klesc, M
    [J]. DISCRETE MATHEMATICS, 2001, 233 (1-3) : 353 - 359
12