Open AccessNon 1-planarity of lexicographic products of graphs
Author(s) -
Naoki Matsumoto,
Yusuke Suzuki
Publication year - 2019
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2231
Subject(s) - planarity testing , lexicographical order , mathematics , combinatorics , conjecture , graph , product (mathematics) , discrete mathematics , geometry
In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K2. This result completes the proof of the conjecture that a graph G ◦ K2 is 1-planar if and only if G has no edge belonging to two cycles.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom