Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
SCIE
SCOPUS
- Title
- Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
- Authors
- Jurisic, A; Koolen, J; Miklavic, S
- Date Issued
- 2005-07
- Publisher
- ACADEMIC PRESS INC ELSEVIER SCIENCE
- 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 = gamma(gamma(2) + 3 gamma + 1), c = gamma(gamma + 1), gamma is an element of 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. We also 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 2d-gon with order (1, k-1). (c) 2005 Elsevier Inc. All rights reserved.
- Keywords
- distance-regular graphs; triangle and pentagon free; Eigen value multiplicity; 2-homogeneous graphs; almost bipartity graphs
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29641
- DOI
- 10.1016/J.JCTB.2005.
- ISSN
- 0095-8956
- Article Type
- Article
- Citation
- JOURNAL OF COMBINATORIAL THEORY SERIES B, vol. 94, no. 2, page. 245 - 258, 2005-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.