On Trees as Star Complements in Regular Graphs

摘要

Let G be a connected r-regular graph (r ---gt--- 3) of order n with a tree of order t as a star complement for an eigenvalue μ ? {?1, 0}. It is shown that n ≤ 1/2 (r + 1)t ? 2. Equality holds when G is the complement of the Clebsch graph (with μ = 1, r = 5, t = 6, n = 16).