The forcing convexity number of a graph

Title:

The forcing convexity number of a graph

Creator:

Chartrand, Gary and Zhang, Ping

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:521b62b6-6b87-47f1-81ea-c6e722e2babf
uuid:521b62b6-6b87-47f1-81ea-c6e722e2babf

Subject:

convex set, convexity number, and forcing convexity number

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

847-858

Source:

Czechoslovak Mathematical Journal | 2001 Volume:51 | Number:4

Harvested from:

CDK

Metadata only:

false