• Title of article

    Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency

  • Author/Authors

    Juri?i?، نويسنده , , Aleksandar and Koolen، نويسنده , , Jack and Miklavi?، نويسنده , , ?tefko، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2005
  • Pages
    14
  • From page
    245
  • To page
    258
  • Abstract
    We classify triangle- and pentagon-free distance-regular graphs with diameter d ⩾ 2 , valency k, and an eigenvalue multiplicity k. In particular, we prove that such a graph is isomorphic to a cycle, a k-cube, a complete bipartite graph minus a matching, a Hadamard graph, a distance-regular graph with intersection array { k , k - 1 , k - c , c , 1 ; 1 , c , k - c , k - 1 , k } , where k = γ ( γ 2 + 3 γ + 1 ) , c = γ ( γ + 1 ) , γ ∈ N , or a folded k-cube, k odd and k ⩾ 7 . This is a generalization of the results of Nomura (J. Combin. Theory Ser. B 64 (1995) 300–313) and Yamazaki (J. Combin. Theory Ser. B 66 (1996) 34–37), where they classified bipartite distance-regular graphs with an eigenvalue multiplicity k and showed that all such graphs are 2-homogeneous. o classify bipartite almost 2-homogeneous distance-regular graphs with diameter d ⩾ 4 . In particular, we prove that such a graph is either 2-homogeneous (and thus classified by Nomura and Yamazaki), or a folded k -cube for k even, or a generalized 2 d -gon with order ( 1 , k - 1 ) .
  • Keywords
    Eigen value multiplicity , 2-homogeneous graphs , Almost bipartity graphs , Distance-regular graphs , Triangle and pentagon free
  • Journal title
    Journal of Combinatorial Theory Series B
  • Serial Year
    2005
  • Journal title
    Journal of Combinatorial Theory Series B
  • Record number

    1527580