Note on Strict-Double-Bound Numbers of Paths, Cycles, and Wheels

Abstract

For a poset $P=(X,{\le }_P)$, the strict-double-bound graph ($sDB$-graph) of $P=(X,{\le }_P)$ is the graph $sDB(P)$ 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 u\le y$ and $x\le v\le y$. The strict-double-bound number $\zeta (G)$ is defined as

$$\zeta (G)=min\{n\mid G\cup N_n\text{ is a strict-double-bound graph}\},$$

where $N_n$ is the graph with $n$ vertices and no edges.

In this paper we deal with strict-double-bound numbers of some graphs. For example, we obtain that

$$\zeta (P_n)=\lceil 2\sqrt{n-1}\rceil \text{ (}n\ge 2\text{)},$$

$$\zeta (C_n)=\lceil 2\sqrt{n}\rceil \text{ (}n\ge 4\text{)},$$

$$\zeta (W_n)=\lceil 2\sqrt{n-1}\rceil \text{ (}n\ge 5\text{)},$$

and

$$\zeta (G+K_n)=\zeta (G)$$

for a graph $G$ with no isolated vertices.