Graph theory results of independence, domination, covering and Turán type

Abstract

We obtain graph theory results of independence, domination, covering or Turán type, most of which are bounds on graph parameters. We first investigate the smallest number λ(G) of vertices and the smallest number λe(G) of edges that need to be deleted from a non-empty graph G so that the resulting graph has a smaller maximum degree. Generalising the classical Turán problem, we then investigate the smallest number λc(G,k) of edges that need to be deleted from a non-empty graph G so that the resulting graph contains no k-clique. Similarly, we address the recent problem of Caro and Hansberg of eliminating all k-cliques of G by deleting the smallest number ι(G,k) of closed neighbourhoods of vertices of G, establishing in particular a sharp bound on ι(G,k) that solves a problem they posed. Similarly to the problem of determining λ(G), the classical domination problem is to determine the size of a smallest set X of vertices of G such that the degree of each vertex v of the graph obtained by deleting X from G is smaller than the degree of v in G (that is, each vertex in V (G)\X is adjacent to some vertex in X). We add the condition that the vertices in V (G)\X have pairwise different numbers of neighbours in X, and we denote the size of X by γir(G). We also consider the further modification that V (G)\X is an independent set of G, and we denote the size of V (G)\X by αir(G). We obtain several sharp bounds on the graph parameters λ(G), λe(G), λc(G,k), ι(G,k), γir(G), and αir(G) in terms of basic graph parameters such as the order, the size, the minimum degree, and the maximum degree of G. We also characterise the extremal structures for some of the bounds.