Graphs with a Minimal Number of Convex Sets

Authors: Jason Brown Ortrud R Oellermann

Publish Date: 2013/09/14

Volume: 30, Issue: 6, Pages: 1383-1397

PDF Link

Abstract

Let G be a graph with vertex set VG A set C of vertices of G is gconvex if for every pair u v in C the vertices on every u–v geodesic ie shortest u–v path belong to C If the only gconvex sets of G are the empty set VG all singletons and all edges then G is called a gminimal graph It is shown that a graph is gminimal if and only if it is trianglefree and if it has the property that the convex hull of every pair of nonadjacent vertices is VG Several properties of gminimal graphs are established and it is shown that every trianglefree graph is an induced subgraph of a gminimal graph Recursive constructions of gminimal graphs are described and bounds for the number of edges in these graphs are given It is shown that the roots of the generating polynomials of the number of gconvex sets of each size of a gminimal graphs are bounded in contrast to their behaviour over all graphs A set C of vertices of a graph is mconvex if for every pair u v in C the vertices of every induced u–v path belong to C A graph is mminimal if it has no mconvex sets other than the empty set the singletons the edges and the entire vertex set Sharp bounds on the number of edges in these graphs are given and graphs that are mminimal are shown to be precisely the 2connected trianglefree graphs for which no pair of adjacent vertices forms a vertex cutset

Keywords: