The forcing hull and forcing geodetic numbers of graphs

摘要

For every pair of vertices u, v in a graph, a u–v geodesic is a shortest path from u to v. For a graph G, let IG[u, v] denote the set of all vertices lying on a u–v geodesic. Let S V(G) and IG[S] denote the union of all IG[u, v] for all u, v ∈ S. A subset S V(G) is a convex set of G if IG[S] = S. A convex hull [S]G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]G = V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if IG[S] = V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number fh (G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number fg(G) of G. In the paper, we construct some 2- connected graph G with (fh (G), fg(G)) = (0, 0), (1, 0), or (0, 1), and prove that, for any nonnegative integers a, b, and c with a + b ≥ 2, there exists a 2-connected graph G with (fh (G), fg (G), h (G), g(G)) = (a, b, a + b + c, a + 2b + c) or (a, 2a + b, a + b + c, 2a + 2b + c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81–94].