On double bound graphs and forbidden subposets |
| |
Authors: | Kenjiro Ogawa |
| |
Affiliation: | Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan |
| |
Abstract: | For a poset P=(X,≤P), the double bound graph (DB-graph) of P is the graph DB(P)=(X,EDB(P)), where xy∈EDB(P) if and only if x≠y and there exist n,m∈X such that n≤Px,y≤Pm. We obtain that for a subposet Q of a poset P,Q is an (n, m)-subposet of P if and only if DB(Q) is an induced subgraph DB(P). Using this result, we show some characterizations of split double bound graphs, threshold double bound graphs and difference double bound graphs in terms of (n, m)-subposets and double canonical posets. |
| |
Keywords: | Double bound graph Forbidden subgraph Forbidden subposet |
本文献已被 ScienceDirect 等数据库收录! |
|