The forcing convexity number of a graph
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 4, pp. 847-858
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
For two vertices $u$ and $v$ of 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 a convex set if $I(S) = S$. The convexity number $\mathop {\mathrm con}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop {\mathrm con}(G)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum convex set containing $T$. The forcing convexity number $f(S, \mathop {\mathrm con})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop {\mathrm con})$ of $G$ is the minimum forcing convexity number among all maximum convex sets of $G$. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph $G$, $f(G, \mathop {\mathrm con}) \le \mathop {\mathrm con}(G)$. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ and $b \ge 3$ is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of $H \times K_2$ for a nontrivial connected graph $H$ is studied.
For two vertices $u$ and $v$ of 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 a convex set if $I(S) = S$. The convexity number $\mathop {\mathrm con}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop {\mathrm con}(G)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum convex set containing $T$. The forcing convexity number $f(S, \mathop {\mathrm con})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop {\mathrm con})$ of $G$ is the minimum forcing convexity number among all maximum convex sets of $G$. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph $G$, $f(G, \mathop {\mathrm con}) \le \mathop {\mathrm con}(G)$. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ and $b \ge 3$ is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of $H \times K_2$ for a nontrivial connected graph $H$ is studied.
@article{CMJ_2001_51_4_a12,
author = {Chartrand, Gary and Zhang, Ping},
title = {The forcing convexity number of a graph},
journal = {Czechoslovak Mathematical Journal},
pages = {847--858},
year = {2001},
volume = {51},
number = {4},
mrnumber = {1864046},
zbl = {0995.05044},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_4_a12/}
}
Chartrand, Gary; Zhang, Ping. The forcing convexity number of a graph. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 4, pp. 847-858. http://geodesic.mathdoc.fr/item/CMJ_2001_51_4_a12/
[bh:dg] F. Buckley and F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, CA, 1990. | MR
[cwz:cn] G. Chartrand, C. E. Wall, and P. Zhang: The convexity number of a graph. (to appear). | MR
[cz:cs] G. Chartrand and P. Zhang: $H$-convex graphs. Math. Bohem. 126 (2001), 209–220. | MR
[hn:cg] F. Harary and J. Nieminen: Convexity in graphs. J. Differential Geom. 16 (1981), 185–190. | DOI | MR
[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. Czechoslovak Math. J. 44 (119) (1994), 173–178. | MR
[n2] L. Nebeský: Characterizing of the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. | MR