Article ID Journal Published Year Pages File Type
4648333 Discrete Mathematics 2012 4 Pages PDF
Abstract

For a poset P=(X,≤P)P=(X,≤P), the strict-double-bound graph (strict DB-graph  sDB(P)) is the graph on XX for which uu is adjacent to vv if and only if u≠vu≠v and there exist elements x,y∈Xx,y∈X distinct from uu and vv such that x≤u≤yx≤u≤y and x≤v≤yx≤v≤y. The strict-double-bound number  ζ(G)ζ(G) of a graph GG is defined as min{l;sDB(P)≅G∪Kl¯ for some poset P}.We obtain strict-double-bound numbers of nearly complete graphs missing one, two or three edges. In particular, we prove that ζ(Kn−e)=3,ζ(Kn−E(P3))=3,ζ(Kn−E(2K2))=4,ζ(Kn−E(K3))=4,ζ(Kn−E(P4))=4,ζ(Kn−E(K1,3))=3,ζ(Kn−E(P3∪K2))=4ζ(Kn−e)=3,ζ(Kn−E(P3))=3,ζ(Kn−E(2K2))=4,ζ(Kn−E(K3))=4,ζ(Kn−E(P4))=4,ζ(Kn−E(K1,3))=3,ζ(Kn−E(P3∪K2))=4 and ζ(K3−E(3K2))=5ζ(K3−E(3K2))=5.

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