IJPAM: Volume 102, No. 1 (2015)

ON STRICT-DOUBLE-BOUND NUMBERS OF
COMPLETE GRAPHS WITHOUT EDGES OF CYCLES

Keisuke Kanada$^1$, Kenjiro Ogawa$^2$, Satoshi Tagusari$^3$, Morimasa Tsuchiya$^4$
$^{1,2,3,4}$Department of Mathematical Sciences
Tokai University
Hiratsuka 259-1292, JAPAN


Abstract. For a poset $P=(X,\leq_P),$ the strict-double-bound graph of $P$ is the graph $\sDB(P)$ on $V(\sDB(P))=X$ for which vertices $u$ and $v$ of $\sDB(P)$ are adjacent if and only if $u \ne v$ and there exist elements $x,y \in X$ distinct from $u$ and $v$ such that $x \leq_P u \leq_P y$ and $x \leq_P v \leq_P y.$ The strict-double-bound number $\zeta(G)$ of a graph $G$ is defined as $\min \{~ n~;~\sDB(P) \cong G \cup \overline{K}_{n}~ {\rm for~ some~ poset}~ P \}$. We obtain upper bounds of strict-double-bound numbers of $K_n-E(C_m)$ $( 5 \leq m \leq n)$.

Received: July 26, 2014

AMS Subject Classification: 05C62

Key Words and Phrases: strict-double-bound graph, strict-double-bound number, cycle

Download paper from here.



DOI: 10.12732/ijpam.v102i1.2 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2015
Volume: 102
Issue: 1
Pages: 9 - 21


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).