Extremal theory for convex matchings in convex geometric graphs (Q1911768)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Extremal theory for convex matchings in convex geometric graphs
scientific article

    Statements

    Extremal theory for convex matchings in convex geometric graphs (English)
    0 references
    2 September 1996
    0 references
    Let \(G_n\) denote a graph whose nodes are the vertices of a convex \(n\)-gon in the plane and whose edges are straight line segments joining some pairs of these vertices. Let \(E_k\) denote any set of \(k\) edges of \(G_n\) such that for each edge \(e\) of \(E_k\), the remaining edges of \(E_k\) all lie on one side of \(e\) (assuming that \(6 \leq 2k \leq n)\). The graph \(G_n\) is \(k\)-saturated if it contains no such set \(E_k\) of edges but loses this property if any new edge is added to \(G_n\). The authors determine the maximum and minimum number of edges such a \(k\)-saturated graph \(G_n\) can have and they characterize the extremal graph, among other things. These results are related to corresponding results on extremal graphs that contain no complete \(k\)-graphs as subgraphs.
    0 references
    extremal graph
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers