Edge-minimal graphs of exponent 2

Abstract

A simple undirected finite graph G has the me_2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. If u and v are adjacent vertices in an me_2-graph G, then either u is the unique common neighbour in G of v and another vertex w, or v is the unique common neighbour in G of u and another vertex w'. If both of these properties hold for every pair of adjacent vertices in G, then we say that G has the strong-me_2-property. The me_2- and strong-me_2-properties can be viewed as relaxations of the friendship property, and this thesis investigates graphs with the me_2- and strong-me_2-properties. The relationship between these properties is discussed, and particular classes of graphs with these properties are described. We also discuss the behaviour of the me_2- and strong-me_2-properties under certain graph products.

It is shown that every graph of order n is an induced subgraph of an me_2-graph of order at most 3n +2. The problem of which graphs can be embedded as induced subgraphs of strong-me_2-graphs is considered, and a construction for complete graphs is presented. The problem of embedding a given graph as an induced subgraph of an me_2-graph or strong-me_2-graph with no edges amongst the additional vertices is studied in detail for trees. Not all graphs can be embedded in this manner. This thesis initiates a study of edge-minimal graphs of exponent 2 and poses some open problems on this subject.