Integration to obtain expressions valid on domains of maximum extent

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G'. In this case G' is said to be a maximum planar induced subgraph of G. We ...

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-...

Erdös [in: Chartrand (Ed.), The Theory and Applications of Graphs, Wiley, New York, 1981, p. 331] conjectured that the vertices of any graph with fewer than (2n+1 2) - (n 2) edges can be split into two parts, both parts inducing subgraphs of maximum ...