Title of article :
Note on strict-double-bound numbers of nearly complete graphs missing some edges
Author/Authors :
Ogawa، نويسنده , , Kenjiro and Soejima، نويسنده , , Ryoko and Tagusari، نويسنده , , Satoshi and Tsuchiya، نويسنده , , Morimasa، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Abstract :
For a poset P = ( X , ≤ P ) , the strict-double-bound graph (strict DB-graph sDB ( P ) ) is the graph on X for which u is adjacent to v if and only if u ≠ v and there exist elements x , y ∈ X distinct from u and v such that x ≤ u ≤ y and x ≤ v ≤ y . The strict-double-bound number ζ ( G ) of a graph G is defined as min { l ; sDB ( P ) ≅ G ∪ K l ¯ for some poset P } .
ain strict-double-bound numbers of nearly complete graphs missing one, two or three edges. In particular, we prove that ζ ( K n − e ) = 3 , ζ ( K n − E ( P 3 ) ) = 3 , ζ ( K n − E ( 2 K 2 ) ) = 4 , ζ ( K n − E ( K 3 ) ) = 4 , ζ ( K n − E ( P 4 ) ) = 4 , ζ ( K n − E ( K 1 , 3 ) ) = 3 , ζ ( K n − E ( P 3 ∪ K 2 ) ) = 4 and ζ ( K 3 − E ( 3 K 2 ) ) = 5 .
Keywords :
Strict-double-bound graph , Strict-double-bound number , Nearly complete graph missing edges
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics