On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars

被引：0
作者：
Clancy K. [1 ]
Haythorpe M. [1 ]
Newcombe A. [1 ]
机构：
[1] 1284 South Road, Tonsley
来源：
Journal of Combinatorial Mathematics and Combinatorial Computing | 2024年 / 119卷
关键词：
Cartesian Product; Crossing Number; Cycle; Path; Small Graphs; Star;
D O I：
10.61091/jcmcc119-31
中图分类号：
学科分类号：
摘要：
There has been significant research dedicated towards computing the crossing numbers of families of graphs resulting from the Cartesian products of small graphs with arbitrarily large paths, cycles and stars. For graphs with four or fewer vertices, these have all been computed, but there are still various gaps for graphs with five or more vertices. We contribute to this field by determining the crossing numbers for fifteen such families. © 2024 the Author(s), licensee Combinatorial Press.
引用
收藏
页码：323 / 333
页数：10
相关论文
共 34 条
  • [1] Garey M.R., Johnson D.S., Crossing number is NP-complete, SIAM Journal on Algebraic Discrete Methods, 4, 3, pp. 312-316, (1983)
  • [2] McQuillan D., Pan S., Richter R.B., On the crossing number of K13, Journal of Combinatorial Theory, Series B, 115, pp. 224-235, (2015)
  • [3] Beineke L.W., Ringeisen R.D., On the crossing numbers of products of cycles and graphs of order four, Journal of Graph Theory, 4, 2, pp. 145-155, (1980)
  • [4] Jendrol S., Scerbova M., On the crossing numbers of S<sub>m</sub> × P<sub>n</sub> and S<sub>m</sub> × C<sub>n</sub>, Casopis pro pestováni matematiky, 107, pp. 225-230, (1982)
  • [5] Klesc M., The crossing numbers of products of paths and stars with 4-vertex graphs, Journal of Graph Theory, 18, 6, pp. 605-614, (1994)
  • [6] Drazenska E., The crossing number of G□C<sub>n</sub> for the graph G on six vertices, Mathematica Slovaca, 61, 5, pp. 675-686, (2011)
  • [7] Drazenska E., Klesc M., The crossing numbers of products of the graph K<sub>2,2,2</sub> with stars, Carpathian Journal of Mathematics, 24, 3, pp. 327-331, (2008)
  • [8] Drazenska E., Klesc M., On the crossing numbers of G□C<sub>n</sub> for graphs G on six vertices, Discrete Mathematics and Graph Theory, 31, 2, pp. 239-252, (2011)
  • [9] Klesc M., On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca, 41, 2, pp. 113-120, (1991)
  • [10] Klesc M., The crossing numbers of certain Cartesian products, Discrete Mathematics and Graph Theory, 15, 1, pp. 5-10, (1995)
1234