$H$-convex graphs

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 -