Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649372 | Discrete Mathematics | 2009 | 6 Pages |
Abstract
For a poset P=(X,≤P)P=(X,≤P), the double bound graph (DB-graph) of PP is the graph DB(P)=(X,EDB(P))DB(P)=(X,EDB(P)), where xy∈EDB(P)xy∈EDB(P) if and only if x≠yx≠y and there exist n,m∈Xn,m∈X such that n≤Px,y≤Pmn≤Px,y≤Pm. We obtain that for a subposet QQ of a poset P,QP,Q is an (nn, mm)-subposet of PP if and only if DB(Q)DB(Q) is an induced subgraph DB(P)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 (nn, mm)-subposets and double canonical posets.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kenjiro Ogawa, Satoshi Tagusari, Morimasa Tsuchiya,