# $H$-convex graphs

Mathematica Bohemica (2001)

• Volume: 126, Issue: 1, page 209-220
• ISSN: 0862-7959

top Access to full text Full (PDF)

## Abstract

top
For two vertices $u$ and $v$ in a connected graph $G$, the set $I\left(u,v\right)$ 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\left(u,v\right)$ for $u,v\in S$ is denoted by $I\left(S\right)$. A set $S$ is convex if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S|=\mathrm{c}on\left(G\right)$. 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 $〈S〉=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\le i\le k$). Also, for every connected graph $H$ of order $k\ge 3$ with convexity number 2, it is shown that there exists an $H$-convex graph of order $n$ for all $n\ge 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\ge N$.

## Citations in EuDML Documents

top

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.