The Forcing Convexity Number of a Graph
Gary Chartrand, Ping Zhang · Czechoslovak Mathematical Journal · 2001
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 ∈ 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) ⩽con( G ). It is shown that every pair a , b of integers with 0 ⩽ a ⩽ b and b ⩾ 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 × K 2 for a nontrivial connected graph H is studied.