The maximal length of 2-path in random critical graphs (Q2336998): Difference between revisions

Summary: Given a graph, its \(2\)-\textit{core} is the maximal subgraph of \(G\) without vertices of degree \(1\). A \(2\)-path in a connected graph is a simple path in its \(2\)-core such that all vertices in the path have degree \(2\), except the endpoints which have degree \(\geqslant 3\). Consider the Erdős-Rényi random graph \(\mathbb{G}(n, M)\) built with \(n\) vertices and \(M\) edges uniformly randomly chosen from the set of \(\left(\begin{matrix} n \\ 2 \end{matrix}\right)\) edges. Let \(\xi_{n, M}\) be the maximum \(2\)-path length of \(\mathbb{G}(n, M)\). In this paper, we determine that there exists a constant \(c(\lambda)\) such that \(\mathbb{E} \left(\xi_{n, \left(n / 2\right) \left(1 + \lambda n^{- 1 / 3}\right)}\right) \sim c(\lambda) n^{1 / 3}\), for any real \(\lambda\). This parameter is studied through the use of generating functions and complex analysis.