Four gravity results (Q864159): Difference between revisions
From MaRDI portal
Latest revision as of 14:07, 25 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Four gravity results |
scientific article |
Statements
Four gravity results (English)
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
planar graph
0 references
path
0 references