Convex hulls of subsets in the join, composition and cartesian product of graphs

Abstract

Given a connected graph G and two vertices u and v in V(G), I _G[u, v] denotes the closed interval consisting of u, v and all vertices lying on some u-v geodesic in G. A subset C of V(G) is convex if I _G[u, v] ⊆ C for every pair of vertices u, v ∈ C. The convex hull of a subset S of V(G), denoted by [S]_G, is the smallest convex set in G containing S. In this paper, we will determine the convex hulls of subsets in the join, composition and cartesian product of two graphs.