The Forcing Convexity Number of a Graph

Authors: Chartrand G.¹; Zhang P.²

Source: Czechoslovak Mathematical Journal, Volume 51, Number 4, December 2001 , pp. 847-858(12)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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

Language: English

Document Type: Regular paper

Affiliations: 1: Dept. of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, U.S.A. chartrand@wmich.edu 2: Dept. of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, U.S.A. ping.zhang@wmich.edu

Publication date: 2001-12-01