Premium
Zip product of graphs and crossing numbers
Author(s) -
Ouyang Zhangdong,
Huang Yuanqiu,
Dong Fengming,
Tay Eng Guan
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22613
Subject(s) - cartesian product , mathematics , combinatorics , bounding overwatch , vertex (graph theory) , product (mathematics) , graph product , discrete mathematics , graph , order (exchange) , 1 planar graph , chordal graph , computer science , geometry , artificial intelligence , finance , economics
D. Bokal proved that the crossing number is additive for the zip product under the condition of having two coherent bundles in the zipped graphs. This property is very effective when dealing with the crossing numbers of (capped) Cartesian product of trees with graphs containing a dominating vertex. In this paper, we first prove that the crossing number is still additive for the zip product under a weaker condition. Based on the new condition, we then establish some general expressions for bounding the crossing numbers of (capped) Cartesian product of trees with graphs (possibly without dominating vertex). Exact values of the crossing numbers of Cartesian product of trees with most graphs of order at most five are obtained by applying these expressions, which extend some previous results due to M. Klešč. In fact, our results can also be applied to deal with Cartesian product of trees with graphs of order more than five.