# $H$-convex graphs

Mathematica Bohemica (2001)

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

## Access Full Article

top## Abstract

top## How to cite

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

## Citations in EuDML Documents

top## NotesEmbed ?

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