Title of article :
On double bound graphs and forbidden subposets
Author/Authors :
Ogawa، نويسنده , , Kenjiro and Tagusari، نويسنده , , Satoshi and Tsuchiya، نويسنده , , Morimasa، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
6
From page :
6353
To page :
6358
Abstract :
For a poset P = ( X , ≤ P ) , the double bound graph (DB-graph) of P is the graph D B ( P ) = ( X , E D B ( P ) ) , where x y ∈ E D B ( P ) if and only if x ≠ y and there exist n , m ∈ X such that n ≤ P x , y ≤ P m . We obtain that for a subposet Q of a poset P , Q is an ( n , m )-subposet of P if and only if D B ( Q ) is an induced subgraph D B ( 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
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1599189
Link To Document :
بازگشت