Global Properties of Graphs with Local Degree Conditions

Let P be a graph property. A graph G is said to be locally P (closed locally P, respectively) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property P. A graph G of order n is said to satisfy Dirac’s condition if �(G) ≥ n/2 and it satisfies Ore’s condition if for every pair u,v of non-adjacent vertices in G, deg(u) + deg(v) ≥ n. A graph is locally Dirac (locally Ore, respectively) if the subgraph induced by the open neighbourhood of every vertex satisfies Dirac’s condition (Ore’s condition, respectively). In this paper we establish global properties for graphs that are locally Dirac and locally Ore. In particular we show that these graphs, of sufficiently large order, are 3-connected. For locally Dirac graphs it is shown that the edge connectivity equals the minimum degree and it is illustrated that this results does not extend to locally Ore graphs. We show that ⌊n/3⌋ − 1 is a sharp upper bound on the diameter of every locally Dirac graph of order n. We show that there exist infinite families of planar closed locally Dirac graphs. In contrast, locally Dirac graphs of sufficiently large order are shown to be non-planar. It is known that every closed locally Ore graph is hamiltonian. We show that locally Dirac graphs have an even richer cycle structure by showing that