For every fixed odd integer k at least 3 and all sufficiently large n, every graph on 2n+1 vertices with n squared plus n plus 1 edges contains two equal-degree vertices joined by a path of length k.
Paths of length five with equal-degree endpoints
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Addressing a question posed by Erd\H{o}s and Hajnal, Chen and Ma proved that, for all $n \ge 600$, the complete bipartite graph $K_{n,n+1}$ is the unique graph on $2n+1$ vertices with at least $n^2+n$ edges that contains no two vertices of equal degree joined by a path of length three. In this paper, we extend this result and show that, for all $n \ge 11$, $K_{n,n+1}$ is the unique $(2n+1)$-vertex graph with at least $n^2+n$ edges that avoids two equal-degree vertices joined by a path of length five. This confirms the very next case of a general conjecture of Chen and Ma on paths of odd length with equal-degree endpoints.
fields
math.CO 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
Large graphs with edge density 1/2 + o(1) contain an ℓ-path between two equal-degree vertices, and this density threshold is tight for odd ℓ.
citing papers explorer
-
A generalization of Erd\H{o}s-Hajnal problem on paths with equal-degree endpoints
For every fixed odd integer k at least 3 and all sufficiently large n, every graph on 2n+1 vertices with n squared plus n plus 1 edges contains two equal-degree vertices joined by a path of length k.
-
The density of graphs with no $\ell$-path connecting equal-degree vertices: a short proof
Large graphs with edge density 1/2 + o(1) contain an ℓ-path between two equal-degree vertices, and this density threshold is tight for odd ℓ.