| Title:
|
$H$-convex graphs (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
126 |
| Issue:
|
1 |
| Year:
|
2001 |
| Pages:
|
209-220 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
convex set |
| Keyword:
|
convexity number |
| Keyword:
|
$H$-convex |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 0977.05044 |
| idMR:
|
MR1826483 |
| DOI:
|
10.21136/MB.2001.133908 |
| . |
| Date available:
|
2009-09-24T21:49:12Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133908 |
| . |
| Reference:
|
[bh:dg] F. Buckley, F. Harary: Distance in Graphs.Addison-Wesley, Redwood City, 1990. MR 1045632 |
| Reference:
|
[chz:geo] G. Chartrand, F. Harary, P. Zhang: On the geodetic number of a graph.(to appear). MR 1871701 |
| Reference:
|
[chz:hn] G. Chartrand, F. Harary, P. Zhang: On the hull number of a graph.(to appear). MR 1796634 |
| Reference:
|
[cwz:cn] G. Chartrand, C. E. Wall, P. Zhang: The convexity number of a graph.Preprint. MR 1913663 |
| Reference:
|
[cz:dgeo] G. Chartrand, P. Zhang: The geodetic number of an oriented graph.Eur. J. Comb. 21 (2000), 181–189. MR 1742433, 10.1006/eujc.1999.0301 |
| Reference:
|
[cz:fcn] G. Chartrand, P. Zhang: The forcing convexity number of a graph.(to appear). MR 1864046 |
| Reference:
|
[cz:fhn] G. Chartrand, P. Zhang: The forcing hull number of a graph.(to appear). MR 1821627 |
| Reference:
|
[cz:cs] G. Chartrand, P. Zhang: Convex sets in graphs.(to appear). MR 1744171 |
| Reference:
|
[es:hn] M. G. Everett, S. B. Seidman: The hull number of a graph.Discrete Math. 57 (1985), 217–223. MR 0816810, 10.1016/0012-365X(85)90174-8 |
| Reference:
|
[hn:cg] F. Harary, J. Nieminen: Convexity in graphs.J. Differential Geom. 16 (1981), 185–190. MR 0638785, 10.4310/jdg/1214436096 |
| Reference:
|
[mu] H. M. Mulder: The expansion procedure for graphs.Contemporary Methods in Graph Theory, R. Bodendiek (ed.), Wissenschaftsverlag, Mannheim, 1990, pp. 459–477. Zbl 0744.05064, MR 1126247 |
| Reference:
|
[m] H. M. Mulder: The Interval Function of a Graph.Mathematisch Centrum, Amsterdam, 1980. Zbl 0446.05039, MR 0605838 |
| Reference:
|
[n1] L. Nebeský: A characterization of the interval function of a connected graph.Czech. Math. J. 44 (1994), 173–178. MR 1257943 |
| Reference:
|
[n2] L. Nebeský: Characterizing of the interval function of a connected graph.Math. Bohem. 123 (1998), 137–144. MR 1673965 |
| . |
