# The forcing convexity number of a graph

Czechoslovak Mathematical Journal (2001)

- Volume: 51, Issue: 4, page 847-858
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topChartrand, Gary, and Zhang, Ping. "The forcing convexity number of a graph." Czechoslovak Mathematical Journal 51.4 (2001): 847-858. <http://eudml.org/doc/30675>.

@article{Chartrand2001,

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 $\mathop \{\mathrm \{c\}on\}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop \{\mathrm \{c\}on\}(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 \{c\}on\})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop \{\mathrm \{c\}on\})$ 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 \{c\}on\}) \le \mathop \{\mathrm \{c\}on\}(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.},

author = {Chartrand, Gary, Zhang, Ping},

journal = {Czechoslovak Mathematical Journal},

keywords = {convex set; convexity number; forcing convexity number; convex set; convexity number; forcing convexity number},

language = {eng},

number = {4},

pages = {847-858},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {The forcing convexity number of a graph},

url = {http://eudml.org/doc/30675},

volume = {51},

year = {2001},

}

TY - JOUR

AU - Chartrand, Gary

AU - Zhang, Ping

TI - The forcing convexity number of a graph

JO - Czechoslovak Mathematical Journal

PY - 2001

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 51

IS - 4

SP - 847

EP - 858

AB - 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 {c}on}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop {\mathrm {c}on}(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 {c}on})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop {\mathrm {c}on})$ 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 {c}on}) \le \mathop {\mathrm {c}on}(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.

LA - eng

KW - convex set; convexity number; forcing convexity number; convex set; convexity number; forcing convexity number

UR - http://eudml.org/doc/30675

ER -

## References

top- Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990. (1990) MR1045632
- The convexity number of a graph, (to appear). (to appear) MR1913663
- $H$-convex graphs, Math. Bohem. 126 (2001), 209–220. (2001) MR1826483
- 10.4310/jdg/1214436096, J. Differential Geom. 16 (1981), 185–190. (1981) MR0638785DOI10.4310/jdg/1214436096
- The Interval Function of a Graph, Mathematisch Centrum, Amsterdam, 1980. (1980) Zbl0446.05039MR0605838
- A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (119) (1994), 173–178. (1994) MR1257943
- Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998), 137–144. (1998) MR1673965

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.