Article ID Journal Published Year Pages File Type
4649372 Discrete Mathematics 2009 6 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,