Geodesic
$H$-convex graphs
Mathematica Bohemica, Tome 126 (2001) no. 1, pp. 209-220

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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 con}(G)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S| = \mathop {\mathrm 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 \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$.
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 con}(G)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $|S| = \mathop {\mathrm 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 \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$.
DOI : 10.21136/MB.2001.133908
Classification : 05C12
Keywords: convex set; convexity number; $H$-convex 
Chartrand, Gary; Zhang, Ping. $H$-convex graphs. Mathematica Bohemica, Tome 126 (2001) no. 1, pp. 209-220. doi: 10.21136/MB.2001.133908
@article{10_21136_MB_2001_133908,
     author = {Chartrand, Gary and Zhang, Ping},
     title = {$H$-convex graphs},
     journal = {Mathematica Bohemica},
     pages = {209--220},
     year = {2001},
     volume = {126},
     number = {1},
     doi = {10.21136/MB.2001.133908},
     mrnumber = {1826483},
     zbl = {0977.05044},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133908/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Zhang, Ping
TI  - $H$-convex graphs
JO  - Mathematica Bohemica
PY  - 2001
SP  - 209
EP  - 220
VL  - 126
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133908/
DO  - 10.21136/MB.2001.133908
LA  - en
ID  - 10_21136_MB_2001_133908
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Zhang, Ping
%T $H$-convex graphs
%J Mathematica Bohemica
%D 2001
%P 209-220
%V 126
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.133908/
%R 10.21136/MB.2001.133908
%G en
%F 10_21136_MB_2001_133908

[bh:dg] F. Buckley, F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, 1990. | MR

[chz:geo] G. Chartrand, F. Harary, P. Zhang: On the geodetic number of a graph. (to appear). | MR

[chz:hn] G. Chartrand, F. Harary, P. Zhang: On the hull number of a graph. (to appear). | MR

[cwz:cn] G. Chartrand, C. E. Wall, P. Zhang: The convexity number of a graph. Preprint. | MR

[cz:dgeo] G. Chartrand, P. Zhang: The geodetic number of an oriented graph. Eur. J. Comb. 21 (2000), 181–189. | DOI | MR

[cz:fcn] G. Chartrand, P. Zhang: The forcing convexity number of a graph. (to appear). | MR

[cz:fhn] G. Chartrand, P. Zhang: The forcing hull number of a graph. (to appear). | MR

[cz:cs] G. Chartrand, P. Zhang: Convex sets in graphs. (to appear). | MR

[es:hn] M. G. Everett, S. B. Seidman: The hull number of a graph. Discrete Math. 57 (1985), 217–223. | DOI | MR

[hn:cg] F. Harary, J. Nieminen: Convexity in graphs. J. Differential Geom. 16 (1981), 185–190. | DOI | MR

[mu] H. M. Mulder: The expansion procedure for graphs. Contemporary Methods in Graph Theory, R. Bodendiek (ed.), Wissenschaftsverlag, Mannheim, 1990, pp. 459–477. | MR | Zbl

[m] H. M. Mulder: The Interval Function of a Graph. Mathematisch Centrum, Amsterdam, 1980. | MR | Zbl

[n1] L. Nebeský: A characterization of the interval function of a connected graph. Czech. Math. J. 44 (1994), 173–178. | MR

[n2] L. Nebeský: Characterizing of the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. | MR

Cité par Sources :