The Maximal Length of 2-Path in Random Critical Graphs

Given a graph, its 2-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 3. Consider the Erds-Rényi random graph G(n,M) built with n vertices and M edges uniformly randomly chosen from the set of n2 edges. Let n,M be the maximum 2-path length of G(n,M). In this paper, we determine that there exists a constant c() such that En,n/21+n-1/3c()n1/3, for any real . This parameter is studied through the use of generating functions and complex analysis.