1989/01/01 by Fan Chung · 3 citations
Mathematics · Computer Science · #Graph theory and applications #Finite Group Theory Research #Advanced Graph Theory Research
paper · pdf · doi:10.1090/s0894-0347-1989-0965008-x
openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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">λ 1,λ 2, … ,λ 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"> | λ 1 | ≥ | λ 2 | ≥ ⋯ ≥ | λ n |</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">λ 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">λ = | λ 2 |</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>