The Maximal Length of 2-Path in Random Critical Graphs

الملخص EN

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 Erdős-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 Eξn,n/21+λn-1/3~c(λ)n1/3, for any real λ.

This parameter is studied through the use of generating functions and complex analysis.