Neighborhood Champions in Regular Graphs

Abstract

For a vertex $x$ in a graph $G$, we define ${\mathrm{\Psi }}_1(x)$ to be the number of edges in the closed neighborhood of $x$. Vertex $x^{\ast }$ is a neighborhood champion if ${\mathrm{\Psi }}_1(x^{\ast })>{\mathrm{\Psi }}_1(x)$ for all $x\ne x^{\ast }$. We also refer to such an $x^{\ast }$ as a unique champion. For $d\ge 4$, let $n_0(1,d)$ be the smallest number such that for every $n\ge n_0(1,d)$ there exists an $n$-vertex $d$-regular graph with a unique champion. Our main result is that $n_0(1,d)$ satisfies $d+3\le n_0(1,d)<3d+1$. We also observe that there can be no unique champion vertex when $d=3$.