×

On convex hulls of graphs. (English) Zbl 0757.05067

Summary: 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.

MSC:

05C35 Extremal problems in graph theory