2026/07/27 by Blas Fernández, Marija Maksimović, Safet Penjić +1
Computer Science · Mathematics · #Finite Group Theory Research #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.1007/s10801-026-01567-y
openalex publication_date 2026/07/27 · openalex created_date 2026/07/28 · openalex updated_date 2026/07/29
Abstract Distance-biregular graphs form a natural bipartite generalization of distance-regular graphs. Among them, the class of 2- Y -homogeneous distance-biregular graphs plays a prominent role and has been the subject of several recent classification efforts. In this paper, we complete the classification of 2- Y -homogeneous (Y,Y') <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>Y</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>Y</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -distance-biregular graphs with eccentricity D=4 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>=</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> . Building on earlier work that settled the cases c2'=1 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> <mml:mo>′</mml:mo> </mml:msubsup> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> and c2'=2 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> <mml:mo>′</mml:mo> </mml:msubsup> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , we address the remaining open case c2'≥ 3 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> <mml:mo>′</mml:mo> </mml:msubsup> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . We prove that no such graphs exist, thereby resolving an open problem posed in previous work and closing the classification program for eccentricity D=4 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>=</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> . Our approach combines a detailed analysis of intersection numbers, arithmetic constraints arising from 2- Y -homogeneity, and structural properties of distance-biregular graphs. As a consequence, we obtain a complete characterization of all 2- Y -homogeneous distance-biregular graphs with D=4 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>=</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> , and we further conclude that every 2- Y -homogeneous distance-biregular graph with c2'≥ 3 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msubsup> <mml:mi>c</mml:mi> <mml:mn>2</mml:mn> <mml:mo>′</mml:mo> </mml:msubsup> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> must necessarily have eccentricity D=3 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> .