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 Erdős-Rényi random graph G(n,M) built with n ver...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2018/8983218 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1110-757X 1687-0042 |