Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420688 | Discrete Applied Mathematics | 2009 | 5 Pages |
For every pair of vertices u,vu,v in a graph, a u–vu–v geodesic is a shortest path from uu to vv. For a graph GG, let IG[u,v]IG[u,v] denote the set of all vertices lying on a u–vu–v geodesic. Let S⊆V(G)S⊆V(G) and IG[S]IG[S] denote the union of all IG[u,v]IG[u,v] for all u,v∈Su,v∈S. A subset S⊆V(G)S⊆V(G) is a convex set of GG if IG[S]=SIG[S]=S. A convex hull [S]G[S]G of SS is a minimum convex set containing SS. A subset SS of V(G)V(G) is a hull set of GG if [S]G=V(G)[S]G=V(G). The hull number h(G)h(G) of a graph GG is the minimum cardinality of a hull set in GG. A subset SS of V(G)V(G) is a geodetic set if IG[S]=V(G)IG[S]=V(G). The geodetic number g(G)g(G) of a graph GG is the minimum cardinality of a geodetic set in GG. A subset F⊆V(G)F⊆V(G) is called a forcing hull (or geodetic) subset of GG if there exists a unique minimum hull (or geodetic) set containing FF. The cardinality of a minimum forcing hull subset in GG is called the forcing hull number fh(G)fh(G) of GG and the cardinality of a minimum forcing geodetic subset in GG is called the forcing geodetic number fg(G)fg(G) of GG. In the paper, we construct some 2-connected graph GG with (fh(G),fg(G))=(0,0),(1,0)(fh(G),fg(G))=(0,0),(1,0), or (0,1)(0,1), and prove that, for any nonnegative integers aa, bb, and cc with a+b≥2a+b≥2, there exists a 2-connected graph GG with (fh(G),fg(G),h(G),g(G))=(a,b,a+b+c,a+2b+c)(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)(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].