On Strict-Double-Bound Numbers of Spiders and Ladders

Abstract

For a poset $P=(X,{\le }_P)$, the strict-double-bound graph ($sDB$-graph $sDB(P)$) is the graph on $X$ for which vertices $u$ and $v$ of $sDB(P)$ are adjacent if and only if $u\ne v$ and there exist $x$ and $y$ in $X$ distinct from $u$ and $v$ such that $x{\le }_{P}y$ and $x{\le }_{P}v{\le }_{P}y$. The strict-double-bound number $\zeta (G)$ of a graph $G$ is defined as $min\{n;G\cup {\overline{K}}_n\text{ is a strict-double-bound graph}\}$.

We obtain that for a spider $S_{n,m}$ ($n,m>3$) and a ladder $L_n$ ($n\ge 4$), $\lceil 2\sqrt{nm}\rceil \le \zeta (S_{n,m})\le n+m$, $\zeta (S_{n,n})=2n$, and $\lceil 2\sqrt{3n+2}\rceil \le \zeta (L_n)\le 2n$.