Premium
Tiled partial cubes
Author(s) -
Brešar Boštjan,
Imrich Wilfried,
Klavžar Sandi,
Mulder Henry Martyn,
Škrekovski Riste
Publication year - 2002
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.10031
Subject(s) - combinatorics , mathematics , regular polygon , graph , discrete mathematics , geometry
In the quest to better understand the connection between median graphs, triangle‐free graphs and partial cubes, a hierarchy of subclasses of partial cubes has been introduced. In this article, we study the role of tiled partial cubes in this scheme. For instance, we prove that almost‐median graphs are tiled and that tiled partial cubes are semi‐median. We also describe median graphs as tiled partial cubes without convex Q 3 −and extend an inequality for median graphs to a larger subclass of partial cubes. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 91–103, 2002