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:

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