Abstract

For a vertex x in a graph G we define Ψ1(x) to be the number of edges in the closed neighborhood of x. Vertex x∗ is a neighborhood champion if Ψ1(x∗)>Ψ1(x) for all x≠x∗. We also refer to such an x∗ as a unique champion. For d≥4 let n0(1,d) be the smallest number such that for every n≥n0(1,d) there exists a n vertex d-regular graph with a unique champion. Our main result is that n0(1,d) satisfies d+3≤n0(1,d)≤3d+1. We also observe that there can be no unique champion vertex when d=3.

Download

Share

COinS