Graphs with a Minimal Number of Convex Sets

• Published in: Graphs and combinatorics 2014-11, Vol.30 (6), p.1383-1397
• Main Authors: Brown, Jason, Oellermann, Ortrud R.
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Combinatorics; Convexity; Engineering Design; Graphs; Hulls (structures); Mathematics; Mathematics and Statistics; Original Paper; Polynomials; Recursive; Roots; Texts
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-013-1356-2

Let G be a graph with vertex set V ( G ). A set C of vertices of G is g - convex if for every pair u , v ∈ C the vertices on every u – v geodesic (i.e. shortest u – v path) belong to C . If the only g -convex sets of G are the empty set, V ( G ), all singletons and all edges, then G is called a g - minimal graph. It is shown that a graph is g -minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V ( G ). Several properties of g -minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g -minimal graph. Recursive constructions of g -minimal 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 g -convex sets of each size of a g -minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m - convex if for every pair u , v ∈ C , the vertices of every induced u – v path belong to C . A graph is m - minimal if it has no m -convex 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 m -minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.