Four gravity results (Q864159)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Four gravity results
scientific article

    Statements

    Four gravity results (English)
    0 references
    0 references
    0 references
    0 references
    13 February 2007
    0 references
    The concept of gravity was introduced by \textit{T.~Madaras} and \textit{R.~Škrekovski} [Discrete Math. 307, 939--951 (2007; Zbl 1111.05027)]. The gravity of a given graph \(H\) in a given family \(\mathcal H\) of graphs is the greatest integer \(n\) with the property that for every integer \(m\) there exists a supergraph \(G\in\mathcal H\) of \(H\), such that each subgraph of \(G\) isomorphic to \(H\) contains at least \(n\) vertices of degree \(\geq m\) in \(G\). T.~Madaras and R.~Škrekovski [loc. cit.] proved that the gravity of the path \(P_k\) in the family of planar graphs of minimum degree \(2\) is at most \(k - 2\) for each \(k\geq 2\), and the gravity reaches the bound of \(k - 2\) for each \(k\notin\{ 5, 7, 8, 9\}\). They conjectured that for each of the four excluded cases the gravity is \(k - 3\). The present paper is devoted to a proof of this conjecture.
    0 references
    0 references
    planar graph
    0 references
    path
    0 references
    0 references