The Maximal Length of 2-Path in Random Critical Graphs

[摘要] Given a graph, its -core is the maximal subgraph ofwithout vertices of degree . A -path in a connected graph is a simple path in its -core such that all vertices in the path have degree , except the endpoints which have degree . Consider the Erdős-Rényi random graphbuilt withvertices andedges uniformly randomly chosen from the set ofedges. Letbe the maximum -path length of . In this paper, we determine that there exists a constantsuch thatThis parameter is studied through the use of generating functions and complex analysis.

[学科分类] 应用数学