Leaves in representation diagrams of bipartite distance-regular graphs

Lang, Michael S.

Journal of Algebraic Combinatorics, Tome 18 (2003) no. 3, pp. 245-254.

Résumé

Summary: Let $Gamma$ denote a bipartite distance-regular graph with diameter $Dge$ 3 and valency $kge$ 3. Let $theta _{0} > theta _{1} ;;; > theta_{ D }$ denote the eigenvalues of $Gamma$ and let $q ^{h} _{ij}$ (0 $le$ h, i, j $le$ D) denote the Krein parameters of $Gamma$. Pick an integer $h$ (1 $le$ h $le$ D - 1). The representation diagram $Delta = Delta_{ h }$ is an undirected graph with vertices 0,1,$\dots , D$. For 0 $le$ i, j $le$ D, vertices i, j are adjacent in $Delta$ whenever i $ne$ j and $q^{h} _{ij} ne$ 0. It turns out that in $Delta$, the vertex 0 is adjacent to $h$ and no other vertices. Similarly, the vertex $D$ is adjacent to D - h and no other vertices. We call 0, $D$ the $trivial$ vertices of $Delta$. Let $l$ denote a vertex of $Delta$. It turns out that $l$ is adjacent to at least one vertex of $Delta$. We say $l$ is a $leaf$ whenever $l$ is adjacent to exactly one vertex of $Delta$. We show $Delta$ has a nontrivial leaf if and only if $Delta$ is the disjoint union of two paths.

Détail

Keywords: primitive idempotent, eigenvalue, association scheme, Q-polynomial, antipodal