# $H$-convex graphs

Mathematica Bohemica (2001)

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

top

## 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$.

## How to cite

top

Chartrand, Gary, and Zhang, Ping. "$H$-convex graphs." Mathematica Bohemica 126.1 (2001): 209-220. <http://eudml.org/doc/248862>.

@article{Chartrand2001,
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 $\mathop \{\mathrm \{c\}on\}(G)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S| = \mathop \{\mathrm \{c\}on\}(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 \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$.},
author = {Chartrand, Gary, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {convex set; convexity number; $H$-convex; convex set; convexity number; -convex},
language = {eng},
number = {1},
pages = {209-220},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {$H$-convex graphs},
url = {http://eudml.org/doc/248862},
volume = {126},
year = {2001},
}

TY - JOUR
AU - Chartrand, Gary
AU - Zhang, Ping
TI - $H$-convex graphs
JO - Mathematica Bohemica
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 126
IS - 1
SP - 209
EP - 220
AB - 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 $\mathop {\mathrm {c}on}(G)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S| = \mathop {\mathrm {c}on}(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 \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$.
LA - eng
KW - convex set; convexity number; $H$-convex; convex set; convexity number; -convex
UR - http://eudml.org/doc/248862
ER -

## References

top
1. Distance in Graphs, Addison-Wesley, Redwood City, 1990. (1990) MR1045632
2. On the geodetic number of a graph, (to appear). (to appear) MR1871701
3. On the hull number of a graph, (to appear). (to appear) MR1796634
4. The convexity number of a graph, Preprint. MR1913663
5. 10.1006/eujc.1999.0301, Eur. J. Comb. 21 (2000), 181–189. (2000) MR1742433DOI10.1006/eujc.1999.0301
6. The forcing convexity number of a graph, (to appear). (to appear) MR1864046
7. The forcing hull number of a graph, (to appear). (to appear) MR1821627
8. Convex sets in graphs, (to appear). (to appear) MR1744171
9. 10.1016/0012-365X(85)90174-8, Discrete Math. 57 (1985), 217–223. (1985) MR0816810DOI10.1016/0012-365X(85)90174-8
10. 10.4310/jdg/1214436096, J. Differential Geom. 16 (1981), 185–190. (1981) MR0638785DOI10.4310/jdg/1214436096
11. The expansion procedure for graphs, Contemporary Methods in Graph Theory, R. Bodendiek (ed.), Wissenschaftsverlag, Mannheim, 1990, pp. 459–477. (1990) Zbl0744.05064MR1126247
12. The Interval Function of a Graph, Mathematisch Centrum, Amsterdam, 1980. (1980) Zbl0446.05039MR0605838
13. A characterization of the interval function of a connected graph, Czech. Math. J. 44 (1994), 173–178. (1994) MR1257943
14. Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998), 137–144. (1998) MR1673965

top

## NotesEmbed?

top

You must be logged in to post comments.

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.