Dept. of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, U.S.A., e-mails: chartrand@wmich.edu; ping.zhang@wmich.edu
Abstract: 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 $\con(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \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, \con)$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \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, \con) \leq\con(G)$. It is shown that every pair $a$, $ b$ of integers with $0 \leq a \leq b$ and $b \geq3$ 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.
Keywords: convex set, convexity number, forcing convexity number
Classification (MSC 2000): 05C12
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade.
To activate your access, please contact Myris Trade at myris@myris.cz.
Subscribers of Springer (formerly Kluwer) need to access the articles on their site, which is http://www.springeronline.com/10587.
