The Maximal Length of 2‐Path in Random Critical Graphs

Vonjy Rasendrahasina, Vlady Ravelomanana and Liva Aly Raonenantsoamihaja

Journal of Applied Mathematics, 2018, vol. 2018, issue 1

Abstract: 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-13/~c(λ)n13/, for any real λ. This parameter is studied through the use of generating functions and complex analysis.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2018/8983218

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2018:y:2018:i:1:n:8983218

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().