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 |