Distance-regular graph

<h2 id="intersection-arrays">Intersection arrays</h2>
<p>The intersection array of a distance-regular graph is the array 
  
    
      
        (
        
          b
          
            0
          
        
        ,
        
          b
          
            1
          
        
        ,
        …
        ,
        
          b
          
            d
            −
            1
          
        
        ;
        
          c
          
            1
          
        
        ,
        …
        ,
        
          c
          
            d
          
        
        )
      
    
    {\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}
  
 in which 
  
    
      
        d
      
    
    {\displaystyle d}
  
 is the diameter of the graph and for each 
  
    
      
        1
        ≤
        j
        ≤
        d
      
    
    {\displaystyle 1\leq j\leq d}
  
, 
  
    
      
        
          b
          
            j
          
        
      
    
    {\displaystyle b_{j}}
  
 gives the number of neighbours of 
  
    
      
        u
      
    
    {\displaystyle u}
  
 at distance 
  
    
      
        j
        +
        1
      
    
    {\displaystyle j+1}
  
 from 
  
    
      
        v
      
    
    {\displaystyle v}
  
 and 
  
    
      
        
          c
          
            j
          
        
      
    
    {\displaystyle c_{j}}
  
 gives the number of neighbours of 
  
    
      
        u
      
    
    {\displaystyle u}
  
 at distance 
  
    
      
        j
        −
        1
      
    
    {\displaystyle j-1}
  
 from 
  
    
      
        v
      
    
    {\displaystyle v}
  
 for any pair of vertices 
  
    
      
        u
      
    
    {\displaystyle u}
  
 and 
  
    
      
        v
      
    
    {\displaystyle v}
  
 at distance 
  
    
      
        j
      
    
    {\displaystyle j}
  
.  There is also the number 
  
    
      
        
          a
          
            j
          
        
      
    
    {\displaystyle a_{j}}
  
 that gives the number of neighbours of 
  
    
      
        u
      
    
    {\displaystyle u}
  
 at distance 
  
    
      
        j
      
    
    {\displaystyle j}
  
 from 
  
    
      
        v
      
    
    {\displaystyle v}
  
.  The numbers 
  
    
      
        
          a
          
            j
          
        
        ,
        
          b
          
            j
          
        
        ,
        
          c
          
            j
          
        
      
    
    {\displaystyle a_{j},b_{j},c_{j}}
  
 are called the intersection numbers of the graph.  They satisfy the equation 
  
    
      
        
          a
          
            j
          
        
        +
        
          b
          
            j
          
        
        +
        
          c
          
            j
          
        
        =
        k
        ,
      
    
    {\displaystyle a_{j}+b_{j}+c_{j}=k,}
  
 where 
  
    
      
        k
        =
        
          b
          
            0
          
        
      
    
    {\displaystyle k=b_{0}}
  
 is the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">valency</a>, i.e., the number of neighbours, of any vertex.
</p><p>It turns out that a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 of diameter 
  
    
      
        d
      
    
    {\displaystyle d}
  
 is distance regular if and only if it has an intersection array in the preceding sense.
</p>
<h2 id="cospectral-and-disconnected-distance-regular-graphs">Cospectral and disconnected distance-regular graphs</h2>
<p>A pair of connected distance-regular graphs are <a href="/facts/Spectral_graph_theory/tBttgGTh">cospectral</a> if their <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrices</a> have the same <a href="/facts/Spectrum_of_a_matrix/BIBnA4qf">spectrum</a>.  This is equivalent to their having the same intersection array.
</p><p>A distance-regular graph is disconnected if and only if it is a <a href="/facts/Graph_Union/5po6Cfac">disjoint union</a> of cospectral distance-regular graphs.
</p>
<h2 id="properties">Properties</h2>
<p>Suppose 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a connected distance-regular graph of valency 
  
    
      
        k
      
    
    {\displaystyle k}
  
 with intersection array 
  
    
      
        (
        
          b
          
            0
          
        
        ,
        
          b
          
            1
          
        
        ,
        …
        ,
        
          b
          
            d
            −
            1
          
        
        ;
        
          c
          
            1
          
        
        ,
        …
        ,
        
          c
          
            d
          
        
        )
      
    
    {\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}
  
. For each 
  
    
      
        0
        ≤
        j
        ≤
        d
        ,
      
    
    {\displaystyle 0\leq j\leq d,}
  
 let 
  
    
      
        
          k
          
            j
          
        
      
    
    {\displaystyle k_{j}}
  
 denote the number of vertices at distance 
  
    
      
        k
      
    
    {\displaystyle k}
  
 from any given vertex and let  
  
    
      
        
          G
          
            j
          
        
      
    
    {\displaystyle G_{j}}
  
 denote the 
  
    
      
        
          k
          
            j
          
        
      
    
    {\displaystyle k_{j}}
  
-regular graph with <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> 
  
    
      
        
          A
          
            j
          
        
      
    
    {\displaystyle A_{j}}
  
 formed by relating pairs of vertices on 
  
    
      
        G
      
    
    {\displaystyle G}
  
 at distance 
  
    
      
        j
      
    
    {\displaystyle j}
  
. 
</p>
<h3>Graph-theoretic properties</h3>
<ul><li>
  
    
      
        
          
            
              k
              
                j
                +
                1
              
            
            
              k
              
                j
              
            
          
        
        =
        
          
            
              b
              
                j
              
            
            
              c
              
                j
                +
                1
              
            
          
        
      
    
    {\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}
  
 for all 
  
    
      
        0
        ≤
        j
        <
        d
      
    
    {\displaystyle 0\leq j<d}
  
.</li>
<li>
  
    
      
        
          b
          
            0
          
        
        >
        
          b
          
            1
          
        
        ≥
        ⋯
        ≥
        
          b
          
            d
            −
            1
          
        
        >
        0
      
    
    {\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}
  
 and 
  
    
      
        1
        =
        
          c
          
            1
          
        
        ≤
        ⋯
        ≤
        
          c
          
            d
          
        
        ≤
        
          b
          
            0
          
        
      
    
    {\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}
  
.</li></ul>
<h3>Spectral properties</h3>
<ul><li>
  
    
      
        G
      
    
    {\displaystyle G}
  
 has 
  
    
      
        d
        +
        1
      
    
    {\displaystyle d+1}
  
 distinct eigenvalues.</li>
<li>The only simple eigenvalue of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is 
  
    
      
        k
        ,
      
    
    {\displaystyle k,}
  
 or both 
  
    
      
        k
      
    
    {\displaystyle k}
  
 and 
  
    
      
        −
        k
      
    
    {\displaystyle -k}
  
 if 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is bipartite.</li>
<li>
  
    
      
        k
        ≤
        
          
            1
            2
          
        
        (
        m
        −
        1
        )
        (
        m
        +
        2
        )
      
    
    {\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}
  
 for any eigenvalue multiplicity 
  
    
      
        m
        >
        1
      
    
    {\displaystyle m>1}
  
 of 
  
    
      
        G
        ,
      
    
    {\displaystyle G,}
  
 unless 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a complete multipartite graph.</li>
<li>
  
    
      
        d
        ≤
        3
        m
        −
        4
      
    
    {\displaystyle d\leq 3m-4}
  
 for any eigenvalue multiplicity 
  
    
      
        m
        >
        1
      
    
    {\displaystyle m>1}
  
 of 
  
    
      
        G
        ,
      
    
    {\displaystyle G,}
  
 unless 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a cycle graph or a complete multipartite graph.</li></ul>
<p>If 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is <a href="/facts/Strongly_regular_graph/0GbdLwSd">strongly regular</a>, then 
  
    
      
        n
        ≤
        4
        m
        −
        1
      
    
    {\displaystyle n\leq 4m-1}
  
 and 
  
    
      
        k
        ≤
        2
        m
        −
        1
      
    
    {\displaystyle k\leq 2m-1}
  
.
</p>
<h2 id="examples">Examples</h2>

<p>Some first examples of distance-regular graphs include:
</p>
<ul><li>The <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a>.</li>
<li>The <a href="/facts/Cycle_graph/bYhnPDHc">cycle graphs</a>.</li>
<li>The <a href="/facts/Odd_graph/ouj27YeI">odd graphs</a>.</li>
<li>The <a href="/facts/Moore_graph/obJmADTb">Moore graphs</a>.</li>
<li>The collinearity graph of a <a href="/facts/Near_polygon/wb3a5FVq">regular near polygon</a>.</li>
<li>The <a href="/facts/Wells_graph/LNFpekUA">Wells graph</a> and the <a href="/facts/Sylvester_graph/ubrNkbjs">Sylvester graph</a>.</li>
<li><a href="/facts/Strongly_regular_graphs/0GbdLwSd">Strongly regular graphs</a> are the distance-regular graphs of diameter 2.</li></ul>
<h2 id="classification-of-distance-regular-graphs">Classification of distance-regular graphs</h2>
<p>There are only finitely many distinct connected distance-regular graphs of any given valency 
  
    
      
        k
        >
        2
      
    
    {\displaystyle k>2}
  
.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p><p>Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity 
  
    
      
        m
        >
        2
      
    
    {\displaystyle m>2}
  
<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> (with the exception of the complete multipartite graphs).
</p>
<h3>Cubic distance-regular graphs</h3>
<p>The <a href="/facts/Cubic_graph/6M32WUIJ">cubic</a> distance-regular graphs have been completely classified.
</p><p>The 13 distinct cubic distance-regular graphs are <a href="/facts/Complete_graph/AYD6hUqI">K4</a> (or <a href="/facts/Tetrahedral_graph/7mkSrl6j">Tetrahedral graph</a>), <a href="/facts/Complete_bipartite_graph/C1RYIdpX">K3,3</a>, the <a href="/facts/Petersen_graph/lLRxXpQs">Petersen graph</a>, the <a href="/facts/Cubical_graph/65lUaAqN">Cubical graph</a>, the <a href="/facts/Heawood_graph/ymqQSkIK">Heawood graph</a>, the <a href="/facts/Pappus_graph/w40dHpA6">Pappus graph</a>, the <a href="/facts/Coxeter_graph/A4DpQ90A">Coxeter graph</a>, the <a href="/facts/Tutte%25E2%2580%2593Coxeter_graph/SH13hLkX">Tutte–Coxeter graph</a>, the <a href="/facts/Dodecahedral_graph/xClYqhcp">Dodecahedral graph</a>, the <a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a>, <a href="/facts/Tutte_12-cage/NrkGdHjh">Tutte 12-cage</a>, the <a href="/facts/Biggs%25E2%2580%2593Smith_graph/UDEzxCPI">Biggs–Smith graph</a>, and the <a href="/facts/Foster_graph/f5Clb9vA">Foster graph</a>.
</p>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Chris_Godsil/ygA2pwGf">Godsil, C. D.</a> (1993). <i>Algebraic Combinatorics</i>. Chapman and Hall Mathematics Series. New York: Chapman and Hall. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-412-04131-0. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1220704">1220704</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "There are only finitely many distance-regular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025. S2CID 18869283. <a href="https://doi.org/10.1016%2Fj.aim.2014.09.025" target="_blank">https://doi.org/10.1016%2Fj.aim.2014.09.025</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Godsil, C. D. (1988-12-01). "Bounding the diameter of distance-regular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683. S2CID 206813795. <a href="/wiki/Combinatorica" target="_blank">/wiki/Combinatorica</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Distance-regular graph open-in-new

Distance-regular graph