On Convex Hulls of Graphs

The convex hull of graph \(G\), a notion born in the theory of random graphs, is the convex hull of the set in \(xy\)-plane obtained by representing each subgraph \(H\) of \(G\) by the point whose coordinates are the number of vertices and edges of \(H\).

In the paper, the maximum number of corners of the convex hull of an \(n\)-vertex graph, bipartite graph, and \(K({r})\)-free graph is found. The same question is posed for strictly balanced graphs.