Advances and Applications in Discrete Mathematics
Volume 1, Issue 2, Pages 215 - 226
(April 2008)
|
|
NOTE ON UPPER BOUND GRAPHS WITH FORBIDDEN SUBGRAPHS
Ayumi Kawamura (Japan), Kenjiro Ogawa (Japan), Satoshi Tagusari (Japan) and Morimasa Tsuchiya (Japan)
|
and xy
is an edge if there exists an element
with
We obtain some properties of a
minimal upper bound graph H which
contains a given graph G as an induced
subgraph. According to these properties, we consider forbidden subgraph
characterizations on some kinds of families of upper bound graphs, that is,
split upper bound graphs, threshold upper bound graphs, etc.