Heavy paths, light stars, and big melons (Q1883260)

A graph \(H\) is defined to be light in a family \(\mathcal H\) of graphs if there exists a finite number \(w(H,\mathcal H)\) such that each \(G\in\mathcal H\) which contains \(H\) as a subgraph, contains also a subgraph \(K\cong H\) such that the sum of the degrees (in \(G\)) of the vertices of \(K\) (that is, the weight of \(K\) in \(G\)) is at most \(w(H,\mathcal H)\). In this paper the authors study the conditions related to the weight of fixed subgraphs of the plane graphs which can enforce the existence of light graphs in some families of plane graphs. For the families of plane graphs \(\mathcal P(w)\) and triangulations \(\mathcal T(w)\) whose edges are of weight (i.e. the sum of the degrees of endvertices) \(\geq w\) they prove among others the following interesting results: 1. The 4-path \(P_4\) is light in \(\mathcal P(w)\) if and only if \(8\leq w\leq 13\). 2. The 3-cycle \(C_3\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\). 3. The 3-cycle \(C_3\) is light in \(\mathcal T(w)\) if and only if \(9\leq w\leq 13\). 4. The 4-cycle \(C_4\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\). 5. The star \(K_{1,4}\) is light in \(\mathcal P(w)\) if and only if \(9\leq w\leq 13\). I. Fabrici and the reviewer proved in [Graphs Comb. 13, 245--250 (1997; Zbl 0891.05025)] that the only light graphs in the family of all 3-connected planar graphs are the paths \(P_k\), for every \(k\geq1\).