Diameters and eigenvalues 论文

摘要

We derive a new upper bound for the diameter of a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> as a function of the eigenvalues of the adjacency matrix. Namely, suppose the adjacency matrix of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has eigenvalues <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda 1 comma lamda 2 comma ellipsis comma lamda Subscript n Baseline"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{\lambda _1},{\lambda _2}, \ldots ,{\lambda _n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue lamda 1 EndAbsoluteValue greater-than-or-equal-to StartAbsoluteValue lamda 2 EndAbsoluteValue greater-than-or-equal-to midline-horizontal-ellipsis greater-than-or-equal-to StartAbsoluteValue lamda Subscript n Baseline EndAbsoluteValue"> <mml:semantics> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo> ≥ </mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo> ≥ </mml:mo> <mml:mo> ⋯ </mml:mo> <mml:mo> ≥ </mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\left | {{\lambda _1}} \right | \geq \left | {{\lambda _2}} \right | \geq \cdots \geq \left | {{\lambda _n}} \right |</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda 1 equals k"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{\lambda _1} = k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda equals StartAbsoluteValue lamda 2 EndAbsoluteValue"> <mml:semantics> <mml:mrow> <mml:mi> λ </mml:mi> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda = \left | {{\lambda _2}} \right |</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Then the diameter <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D left-parenthesis upper G right-parenthesis"> <mml:semantics>