**
MATHEMATICA BOHEMICA, Vol. 126, No. 1, pp. 209-220 (2001)
**

# $H$-convex graphs

## Gary Chartrand, Ping Zhang

* Gary Chartrand, Ping Zhang*, Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ` zhang@math-stat.wmich.edu`

**Abstract:**
For two vertices $u$ and $v$ in a connected graph $G$, the set $I(u, v)$ consists of all those vertices lying on a $u-v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I(u,v)$ for $u, v \in S$ is denoted by $I(S)$. A set $S$ is convex if $I(S) = S$. The convexity number $\con (G)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S| = \con (G)$. The cardinality of a maximum convex set in a graph $G$ is the convexity number of $G$. For a nontrivial connected graph $H$, a connected graph $G$ is an $H$-convex graph if $G$ contains a maximum convex set $S$ whose induced subgraph is $\langle {S}\rangle = H$. It is shown that for every positive integer $k$, there exist $k$ pairwise nonisomorphic graphs $H_1, H_2, \cdots , H_k$ of the same order and a graph $G$ that is $H_i$-convex for all $i$ ($1 \leq i \leq k$). Also, for every connected graph $H$ of order $k \geq 3$ with convexity number 2, it is shown that there exists an $H$-convex graph of order $n$ for all $n \geq k+1$. More generally, it is shown that for every nontrivial connected graph $H$, there exists a positive integer $N$ and an $H$-convex graph of order $n$ for every integer $n \geq N$.

**Keywords:** convex set, convexity number, $H$-convex

**Classification (MSC2000):** 05C12

**Full text of the article:**

[Previous Article] [Next Article] [Contents of this Number]

*
© 2005 ELibM and
FIZ Karlsruhe / Zentralblatt MATH
for the EMIS Electronic Edition
*