FORCING SUBSETS FOR SOME TYPES OF CONVEX SETS IN A GRAPH

Abstract

Let G be a connected graph. Given any two vertices u and v of G, the set ID[ ] u, consists of all those vertices lying on a longest v u-v path. A set S is a detour convex set if ID[u, for v] ⊆ S u, v ∈ S. A tolled walk T between distinct vertices u and v of G is a walk of the form [ ] , , ..., , , 1 T u w w v = k where k ≥ 1, in which w1 and w2 are the only neighbors of u and v in T, respectively. The toll interval TG (u, v) is the set of vertices in G that lie on some u-v walk. A subset S ⊆ V( ) G is toll convex (or t-convex) if TG (u, for all v) ⊆ S u, v ∈ S. In this paper, we define and study the concepts of detour convexity number, toll convexity number, forcing subset for a maximum detour convex (maximum toll convex) set, and the forcing detour convexity (forcing toll convexity) number of a graph. In particular, we study these concepts in the join and corona of graphs.