close

Вход

Забыли?

вход по аккаунту

?

352

код для вставкиСкачать
From Regular Boundary
Graphs to Antipodal
Distance-Regular Graphs*
M. A. Fiol, E. Garriga, and J. L. A. Yebra
DEPARTAMENT DE MATEMA?TICA APLICADA I TELEMA?TICA
UNIVERSITAT POLITE?CNICA DE CATALUNYA
E-mails: f iol@mat.upc.es, garriga@mat.upc.es, yebra@mat.upc.es
Received April 10, 1995; revised October 16, 1997
Abstract: Let ? be a regular graph with n vertices, diameter D, and d + 1
different eigenvalues ? > ?1 > и и и > ?d . In a previous paper, the authors
showed that if P (?) > n ? 1, then D ? d ? 1, where P is the polynomial of
degree d?1 which takes alternating values ▒1 at ?1 , . . . , ?d . The graphs satisfying
P (?) = n ? 1, called boundary graphs, have shown to deserve some attention
because of their rich structure. This paper is devoted to the study of this case
and, as a main result, it is shown that those extremal (D = d) boundary graphs
where each vertex have maximum eccentricity are, in fact, 2-antipodal distanceregular graphs. The study is carried out by using a new sequence of orthogonal
polynomials, whose special properties are shown to be induced by their intrinsic
c 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123?140, 1998
symmetry. Keywords: antinodal distance-regular graphs, boundary graphs, eigenvalues, orthogonal
polynomials
1. INTRODUCTION
A general problem which has deserved much attention among graph theorists is to
*Work supported in part by the Spanish Research Council (Comisio?n Interministerial
de Ciencia y Tecnologia, CICYT) under projects TIC 92-1228-E and TIC 94-0592.
c
1998 John Wiley & Sons, Inc.
CCC 0364-9024/98/030123-18
124 JOURNAL OF GRAPH THEORY
know how the properties of a graph depend on its (adjacency matrix) spectrum. In
this context, some results relating the diameter of a regular graph and its second
eigenvalue (in absolute value) have been recently given by Chung [4], Delorme and
Sole? [6] and Mohar [11]. As it was pointed out in [7], the results in [4, 6] admit the
following unified presentation. Let ? > ?1 > и и и > ?d be the distinct eigenvalues
of a regular graph ? of order n and diameter D(?). It is well known that D(?) ? d.
Let p ? Rk [x], the vector space of real polynomials of degree at most k ? d ? 1.
Then,
p(?) > kpk? (n ? 1) ? D(?) ? dgr p ? k
(1)
where kpk? = max1?l?d {|p(?l )|}. Similar results concerning the spectrum of the
Laplacian matrix were also given for (not necessarily regular) graphs by Chung,
Faber and Manteuffel [5] using Tchebychef polynomials. Following these works,
the authors [7] optimized previous results by introducing a new class of polynomials,
called the k -alternating polynomials because of their special behavior on the mesh
M = {?1 , . . . , ?d }. More precisely they showed that, for a regular graph on n
vertices,
(2)
Pk (?) > n ? 1 ? D(?) ? k
where Pk ? Rk [x] denotes the k -alternating polynomial defined by the condition:
Pk (?) = sup {p(?) : kpk? ? 1}.
p?Rk [x]
In [7] it was shown that the k -alternating polynomial Pk is unique and its degree
is exactly k . Moreover, Pd?1 ? P , called the alternating polynomial for short, is
characterized by P (?l ) = (?1)l+1 , l = 1, . . . , d, and hence an easy computation
gives:
P (?) =
d
X
?0
i=1
?i
,
d
Y
where ?i =
|?i ? ?l |,
i = 0, 1, . . . , d.
(3)
l=0(l=i)
/
See [7] for more details.
The above results suggest the issue of analyzing the graphs which are on the
boundary of the region in which the condition on the lefthand side of (2) holds.
Namely, those regular graphs satisfying Pk (?) = n ? 1, which we call k -boundary
graphs. In the?apparently more tractable?case k = d ? 1, we simply speak of
boundary graphs. Notice that, from their definition and (3), boundary graphs are
characterized by
P (?) + 1 =
d
X
?0
l=0
?l
= n.
(4)
The study of such graphs was initiated by the authors in [8, 9], where some of
their basic properties were discussed. Also, some constructions of such graphs
ANTIPODAL DISTANCE-REGULAR GRAPHS 125
were presented. In particular, it was shown that there are boundary graphs with
diameter D ? d ? 1, but there are also graphs with spectrally maximum diameter
D = d, which we call below extremal. Then, it was proved that all 2-antipodal
distance-regular graphs are extremal boundary graphs. Unfortunately, the converse
result does not hold. Thus, the Hoffman graph [10], which is cospectral with the (2antipodal distance-regular) graph Q4 ?the 4-cube?is an example of an extremal
boundary graph which is not distance-regular. In fact, since the characterization (4)
of boundary graphs only takes into account the (distinct) eigenvalues and the order of
the graph, all cospectral graphs of a boundary graph are also boundary graphs. Like
Q4 , the Hoffman graph has diameter 4 and is therefore extremal. However, unlike
the 4-cube, not all the vertices of the Hoffman graph have eccentricity equal to the
diameter. A natural question is then to ask whether every extremal boundary graph
having all vertices with maximum eccentricity is a 2-antipodal distance-regular
graph. The main contribution of this paper is to give an affirmative answer to such
a question. Our study is mainly based on a new class of orthogonal polynomials,
which are the topic of Section 2. Their special properties, inherited from their
intrinsic symmetry, suggest that their interest might go beyond our applications,
which begin in Section 3 for general boundary graphs. In the same section we
show that there are some parallelism between our study and part of the theory on
distance-regular graphs. The close relationship between extremal boundary graphs
and 2-antipodal distance-regular graphs is explored in Section 4.
The rest of this section is devoted to establish the main terminology, and to
recall some additional known results used throughout the paper. Thus, ? = (V, E)
denotes a simple, connected graph, of order |V | = n, and regular of degree ?. For
a given ordering of its vertices, we only distinguish between a vertex ei and the
corresponding vector ei of the canonical base of Rn by the bold type used. Besides,
we consider A, the adjacency matrix of ?, as an endomorphism of Rn . As usual, J
denotes the nОn matrix with all entries equal to 1, and similarly j ? Rn is the all-1
vector. The eigenvalues of the graph are denoted by ?0 > ?1 > и и и > ?d (we will
assume that ? is not the complete graph, so that d ? 2) but, because of its special
role, the largest eigenvalue ?0 is also denoted by ?. The spectrum of the graph,
which is the set of eigenvalues together with their multiplicities mi = m(?i ), is
md
m1
0
denoted by Spec ? = {?m
0 , ?1 , . . . , ?d }. The distance between two vertices is
denoted by ?(ei , ej ) and the diameter is represented by D(?). A vertex ei is said
to be diametral whenever there exists a vertex ej such that ?(ei , ej ) = D(?), and
then {ei , ej } will be referred to as a diametral pair of vertices. In this case, any
shortest path between ei and ej is called a diametral path of ?. The graph is called
diametral when all its vertices are diametral. It is well known that D(?) ? d and
when D(?) = d we say that ? is an extremal graph. As usual, ?l (e) denotes the
set of vertices at distance l from e and ?l is the graph on V where two vertices are
adjacent whenever they are at distance l in ?.
A generic polynomial p operates on Rn by the rule pw = p(A)w, and the
matrix is not specified unless some confusion may arise. Let Z + and Z ? denote
the monic polynomials having as roots the eigenvalues ?l , 1 ? l ? d, with odd
126 JOURNAL OF GRAPH THEORY
and even subindex l, respectively. Then, we will make ample use of the following
spectral decompositions of the canonical vector ei .
ei =
1
1
1
?
j + zi = j + z i1 + и и и + z id = j + z +
i + zi
n
n
n
(5)
?
+
?
where z i ? j ? , z il ? Ker (x ? ?l ), z +
i ? Ker Z and z i ? Ker Z .
Since for a boundary graph the inequality in the righthand side of (2) (with
k = d ? 1) does not hold, the matrix P (A) may have entries equal to zero. That
is, it may happen that hP e, e?i = 0 for some pair of vertices e, e?. We say in this
case that each one is a conjugate vertex and, when they are different, that they form
a pair of conjugate vertices. Thus, every diametral pair of an extremal graph is a
conjugate pair. If hP e, ei = 0 we say that e is a selfconjugate vertex.
In some cases, condition (4) characterizing boundary graphs is strong enough to
determine the entries of the matrix P (A), from where some of the main properties
of such graphs follow. Indeed, since the alternating polynomial satisfies P (?l ) =
(?1)l+1 , 1 ? l ? d, we have kP z i k2 = kz i k2 = 1 ? k n1 jk2 = 1 ? n1 , and this
decomposition allows us to give a generic expression for the ij entry of the matrix
P (A), as follows:
(P (A))ij = hP ei , ej i =
P (?)
1
j + P zi, j + zj
n
n
n?1
+ kP z i k kz j k cos ?ij
n
n?1
=
(1 + cos ?ij )
n
=
(6)
where ?ij represents the angle formed by P z i and z j .
As a straightforward consequence of (6), note that all the entries of P (A) satisfy
0 ? (P (A))ij < 2(1 ? n1 ). Furthermore,
(7)
(P (A))ij = 0 ? P z i = ?z j
+ ?
?
l
? z+
i = ?z j , z i = z j ? z il = (?1) z jl ,
(
?
(1 ? l ? d) (8)
ei = n1 j + z i1 + z i2 + z i3 + и и и + z id
ej = n1 j ? z i1 + z i2 ? z i3 + и и и + (?1)d z id
(9)
since, in j ? , P z = z iff z ? Ker Z + , and P z = ?z iff z ? Ker Z ? .
Notice that, by (9), the spectral decompositions of the conjugate vertices ei , ej
have the same components, except for their signs which are alternatively equal or
distinct. As we will see, the polynomials studied in the next section show a similar
behavior at the points of the mesh and, we could say that, in a sense, each one has
also a ??conjugate.?? For instance, consider the pair (P, I) formed by the alternating
and the identity polynomials respectively. Then, using (9) we get
P ei + Iej =
1
(P j + j) = j.
n
(10)
ANTIPODAL DISTANCE-REGULAR GRAPHS 127
That is, if P ei has a zero component, all its other components are 1, and hence
each vertex can only belong to a pair of conjugate vertices. Let V ? denote the set
of conjugate vertices and let ?? be its induced subgraph in V ? . Let ? : V ? ? V ?
be the mapping defined by ?e = (J ? P (A))e. From the above, ? is well defined
and it is an involutive permutation of V ? . Then, in [8] the following result was
proved.
Proposition 1.1. In a boundary graph ? the mapping ? is an automorphism of
?? . Moreover, in ?, ?(?ei , ?ej ) = ?(ei , ej ), ?ei , ej ? V ? .
2. A CLASS OF ORTHOGONAL POLYNOMIALS
Let M = {x1 > и и и > xm } be a mesh of m real points. For i = 1, . . . , m, set
Mi = {1, . . . , m} \ {i} and
?i (M) =
Y
?i (M) = (?1)i+1 ?i = |?i (M)|.
(xi ? xl ),
l?Mi
Using the fact that each polynomial of degree ? m ? 1 can be identified by its
values on M, we introduce in Rm?1 [x] a scalar product by
m
X
hp, qi =
i=1
1
p(xi )q(xi ),
?i (M)
and a linear mapping T by
(T p)(xi ) = (?1)i+1 p(xi ),
i = 1, . . . , m.
Clearly, T is an involutive automorphism of Rm?1 [x], and for this scalar product
we have:
P
(?1)i+ 1
(a) T is symmetric, hT p, qi = m
i=1 ?i (M) p(xi )q(xi ) = hp, T qi;
(b) T is an isometry, hT p, T qi = hT 2 p, qi = hp, qi. In particular, kT pk = kpk.
In order to establish the main results of this section we first need the following.
Lemma 2.1.
m
X
i=1
xki
=
?i (M)
0 for k = 0, 1, . . . , m ? 2
1 for k = m ? 1.
Proof. Since for polynomials of degree ? m ?
1 interpolation trough m points
Q
is exact, using Lagrange interpolation with Ri = j?Mi (x ? xj ) we have
p=
m
X
p(xi )
i=1
Ri (xi )
Ri =
m
X
p(xi )
i=1
and for p = xk the result follows.
?i (M)
Ri =
m
X
p(xi )
i=1
?i (M)
!
xm?1 + и и и
128 JOURNAL OF GRAPH THEORY
P
1
i+1 xr xs =
Noticing that hT xr , xs i = m
i=1 ?i (M) (?1)
i i
restate the above lemma in the following way:
r
s
hT x , x i =
Pm
s
xr+
i
i=1 ?i (M) ,
we may
0 for r + s = 0, 1, . . . , m ? 2
1 for r + s = m ? 1.
(11)
We next use T to characterize some systems of orthogonal polynomials for the
scalar product above.
Proposition 2.2.
Let pk , k = 0, . . . , m ? 1, be polynomials with dgr pk = k.
Then, the following statements are equivalent:
(i) {pk , k = 0, . . . , m ? 1} is an orthogonal system;
(ii) T pk is proportional to pm?1?k , k = 0, 1, . . . , m ? 1.
Proof. Since dgr pk = k , (11) implies
hT pk , pl i = 0 for k + l < m ? 1.
Let {pk , k = 0, . . . , m ? 1} be an orthogonal system. Then,
T pk =
m?1
X
l=0
ckl pl =
m?1
X
ckl pl ,
l=m?1?k
since for l < m ? 1 ? k we have ckl kpl k2 = hT pk , pl i = 0. For k = 0 we
already obtain that T p0 is proportional to pm?1 . Using induction, let us assume
that T p0 = ?0 pm?1 , . . . , T pk?1 = ?k?1 pm?k . Consider now l > m?1?k . Since
T is involutive and m?1?l < k , we obtain pm?1?l = T 2 (pm?1?l ) = ?m?1?l T pl ,
so that
1
ckl kpl k2 = hT pk , pl i = hpk , T pl i =
hpk , pm?1?l i = 0.
?m?1?l
Therefore, ckl = 0 for l > m ? 1 ? k and T pk is proportional to pm?1?k .
Reciprocally, assume now that T pk = ?k pm?1?k , for k = 0, 1, . . . , m ? 1. For
0 ? j < i ? m ? 1 we have m ? 1 ? i + j < m ? 1, so that
hpi , pj i = hT pi , T pj i = ?i hpm?1?i , T pj i = 0.
From this proposition we obtain, for k = 0, 1, . . . , m ? 1,
kpk k2 = hT pk , T pk i = ?k2 kpm?1?k k2 ,
kpk k2 = hT pk , ?k pm?1?k i
= ?k hT (?k xk + и и и), ?m?1?k xm?1?k + и и иi = ?k ?k ?m?1?k ,
(12)
(13)
where ?k is the leading coefficient of pk , 0 ? k ? m ? 1.
Proposition 2.3.
For any given x0 > x1 and any constant n there exists a
unique system of orthogonal polynomials on the mesh M, w0 , w1 , . . . , wm?1 , with
dgr wk = k, such that, for k = 0, 1, . . . , m ? 1,
ANTIPODAL DISTANCE-REGULAR GRAPHS 129
(a) T wk = wm?1?k ;
(b) wk (x0 ) + wm?1?k (x0 ) = n.
Proof. The Gram-Schmidt procedure assures the existence of a unique system
of orthonormal polynomials q0 , q1 , . . . , qm?1 , such that dgr qk = k and the leading
coefficient of each qk is positive. From the theory of orthogonal polynomials we
know that all their roots are real and belong to the interval (xm , x1 ). It follows
that qk (x0 ) > 0 for all k . From (12) and (13) we obtain T qk = qm?1?k . Setting
wk = ?k qk we have
T wk = ?k T qk = ?k qm?1?k =
?k
?m?1?k
wm?1?k .
Now (a) is equivalent to ?k = ?m?1?k and (b) becomes
n = ?k qk (x0 ) + ?m?1?k qm?1?k (x0 ) = (qk (x0 ) + qm?1?k (x0 ))?k ,
which determines ?k for k = 0, 1, . . . , m ? 1.
In particular, (a) gives
kwk k2 = ?k ?m?1?k , ,
k = 0, 1, . . . , m ? 1,
(14)
where ?k is the leading coefficient of wk . Denoting by PM the polynomial of
degree m ? 1 such that PM (xi ) = (?1)i+1 , i = 1, . . . , m, we have: wm?1 (xi ) =
T w0 (xi ) = (?1)i+1 ?0 , so that wm?1 = ?0 PM . Moreover, ?0 + ?0 PM (x0 ) = n,
and
n
n
w0 =
(15)
,
wm?1 =
PM .
1 + PM (x0 )
1 + PM (x0 )
Notice that when M, x0 , n are such that PM (x0 ) = n ? 1, equation (15) becomes
w0 = 1 and wm?1 = PM . We will consider this case in the context of graphs in
the next section.
Consider now two meshes
M? = {?1 > и и и > ?d },
M = {?0 (= ?) > ?1 > и и и > ?d }.
For the mesh M? (resp. M) we define the involutive automorphism T ? (resp. T )
and consider the scalar product h , i? (resp. h , i) and the norm k и k? (resp. k и k.)
We also write ?i? = ?i (M? ) and ?i = ?i (M).
For a fixed constant n let w0 , w1 , . . . , wd?1 be the orthogonal system of Proposition 2.3 for the mesh M? with x0 = ?, that is T ? wk = wd?1?k , wk (?) +
wd?1?k (?) = n for k = 0, 1, . . . , d ? 1. We next introduce the polynomials
in Rd [x]:
vk = wk ? wk?1 ,
by defining w?1 = 0, wd =
and w?1 (?) + wd (?) = n.
n
?0
Qd
i=1 (x
k = 0, 1, . . . , d,
? ?i ), so that we still have: T ? w?1 = wd
130 JOURNAL OF GRAPH THEORY
Proposition 2.4. The polynomials v0 , v1 , . . . , vd form an orthogonal system for
the mesh M. Moreover, kvk k2 = ?k ?d?k , k = 0, 1, . . . , d, where ?k denotes the
leading coefficient of vk .
Proof. For k = 0, . . . , d, we have
(T vk )(?i ) = (?1)i (wk (?i ) ? wk?1 (?i ))
= (?1)i (T ? wd?1?k (?i ) ? T ? wd?k (?i ))
= wd?k (?i ) ? wd?k?1 (?i ) = vd?k (?i ),
i = 1, . . . , d;
(T vk )(?) = vk (?) = wk (?) ? wk?1 (?)
= n ? wd?1?k (?) ? n + wd?k (?) = vd?k (?),
so that T vk = vd?k , for k = 0, 1, . . . , d and the result follows from Proposition
2.2. The value of kvk k2 comes from (14).
Lemma 2.5.
The scalar products in the two meshes M? and M are related by:
hf, gi? = ?hf, gi ? hxf, gi.
Proof. hf, gi? =
hxf, gi.
Proposition 2.6.
relation:
Pd
1
l=1 ? ? f (?l )g(?l )
l
=
Pd
l=0
???l
?l f (?l )g(?l )
= ?hf, gi ?
The polynomials v0 , v1 , . . . , vd satisfy the following recurrence
xv0 = v?1 + a0 v0 + c1 v1
xvi = bi?1 vi?1 + ai vi + ci+1 vi+1 (i = 1, . . . , d ? 1)
xvd = bd?1 vd?1 + ad vd + vd+1
(16)
where v?1 = 0, vd+1 = ?n0 (x ? ?0 )(x ? ?1 ) и и и (x ? ?d ) and, setting ??1 = 0 the
coefficients are given by
?i?1
?d?i?1
ci =
,
bi =
,
ai = ? ? bi ? ci ,
(i = 0, . . . , d).
?i
?d?i
Proof. From the recursive relation satisfied by orthogonal polynomials, and
equaling the leading coefficients, we have
xvi =
hxvi , vi?1 i
hxvi , vi i
?i
vi?1 +
vi +
vi+1 .
2
2
kvi?1 k
kvi k
?i+1
Then, from (14) we get kvi k2? = kwi k2? + kwi?1 k2? = ?i ?d?1?i + ?i?1 ?d?i . By
Proposition 2.4 and Lemma 2.5 we have
bi =
hxvi+1 , vi i
1
kwi k2?
?d?i?1
=
?
hv
,
v
i
=
=
i+1
i
?
2
kvi k
?i ?d?i
?i ?d?i
?d?i
ANTIPODAL DISTANCE-REGULAR GRAPHS 131
ai =
hxvi , vi i
1
?d?i?1 ?i?1
=
(?kvi k2 ? kvi k2? ) = ? ?
?
= ? ? bi ? ci
2
kvi k
?i ?d?i
?d?i
ai
Notice that Proposition 2.6 can also be stated as a matrix equation in the following
way:
??
?
a0 c1
?b a c
? 0 1 2
?
b1 a2 и
?
?
b2 и и
?
?
?
и и
?
?
и
и
и
?
v0
v1
v2
и
и
??
??
??
??
??
??
??
??
??
cd ? ? vd?1
bd?1 ad
vd
?
v0
v1
v2
и
и
?
?
?
?
?
?
?
?
?
?
? = x?
?
?
?
?
?
?
?
? vd?1
?
?
? ?
? ?
? ?
? ?
? ?
???
? ?
? ?
? ?
? ?
vd
0
0
0
и
и
0
?
?
?
?
?
?
? . (17)
?
?
?
?
vd+1
Then, the (d + 1) О (d + 1) tridiagonal matrix of coefficients, denoted by B , has
as simple eigenvalues the roots of vd+1 , that is ?0 (= ?) > ?1 > и и и > ?d , with
associated eigenvectors v(?i ) = (v0 (?i ), . . . , vd (?i ))T .
Propositions 2.3 and 2.4 lead to an inductive procedure for constructing the polynomials v0 , v1 , . . . , vd on a given mesh M = {?0 (= ?) > ?1 > и и и > ?d }. If
Mk ? {?k > и и и > ?d } for k = 0, . . . , d?1, let Vk = {v0 , . . . , vd?k }Mk (Proposition 2.4) and Wk = {w0 , . . . , wd?k?1 }Mk (Proposition 2.3) be the corresponding
orthogonal sequences associated to Mk . Consider now the steps of the following
diagram:
?
?
Vk ?k Wk ?k Vk?1
Then, we construct V0 = {v0 , . . . , vd }M by applying ?0 ??0 ?и и и??d?1 ??d?1 ??d
to Wd = {w0 }Md .
3. ORTHOGONAL POLYNOMIALS IN BOUNDARY AND
DISTANCE-REGULAR GRAPHS
Let G be a graph on n vertices, with distinct eigenvalues ? = ?0 > ?1 >
и и и > ?d . Consider the systems of orthogonal polynomials w0 , w1 , . . . , wd?1 and
v0 , v1 , . . . , vd of the preceding section, corresponding to the meshes M? = {?1 >
и и и > ?d } and M = {?(= ?0 ) > ?1 > и и и > ?d }, respectively, for such a n.
Notice that, since M consist of the eigenvalues of G, we have:
Lemma 3.1. (a) wd is the Hoffman polynomial [10] of ?, that is, wd (A) = J;
(b) w0 = 1 and wd?1 = P (alternating polynomial of ?) if and only if ? is a
boundary graph.
Proof. (a) is a well known result for a regular connected graph. Furthermore,
(b) follows from (15) by taking PM = P .
132 JOURNAL OF GRAPH THEORY
Now, define the numbers ki , i = 0, 1, . . . , kd recursively by ki =
initialized with k0 = v0 (?) = 1. Then,
ki =
bi?1
ci ki?1 ,
bi?1
bi?1 и и и b0
?d?i ?i
?0
ki?1 =
=
=
kvi k2 .
ci
ci и и и c1
?d ?0
n
(18)
Let us now turn our attention to distance-regular graphs. As it is well known,
a graph ?, with adjacency matrix A and eigenvalues ? > ?1 > и и и > ?d , is
a distance-regular graph if and only if its adjacency algebra (that is, the algebra
generated by its adjacency matrix) contains the adjacency matrix of ?k , for any
1 ? k ? d, and this matrix is a polynomial of degree k in A, see Biggs [2]
and Brouwer et al. [3]. In other words, there exists a sequence of polynomials
{vk , 0 ? k ? d} such that dgr vk = k and
(vk (A))ij =
1, if ?(ei , ej ) = k
0, otherwise,
(19)
which are usually called the (k -)distance polynomials. These polynomials satisfy
the recurrence relation (16), where the coefficients ai , bi , ci are now the entries
of the so-called intersection array of ?. Besides, the matrix B associated to the
recurrence relation (17) is now the collapsed adjacency matrix of ?. See [2, 3] for
more details.
A known, but seldom explicited, result states that the distance polynomials constitute an orthogonal basis of Rd [x] with the scalar product
hf, gi =
d
X
m(?l )
l=0
n
f (?l )g(?l ).
(20)
An easy proof of such result goes as follows. By (19), all entries of the main
diagonal of vi (A)vj (A), i =
/ j , are equal to zero, and hence Tr(vi (A)vj (A)) = 0.
On the other hand, since each vi (A) is a polynomial in A so is vi (A)vj (A), and
therefore
0 = Tr(vi (A)vj (A)) =
d
X
m(?l )vi (?l )vj (?l ) = nhvi , vj i.
l=0
Furthermore, for i = j we get
kvi k2 = hvi , vi i =
1
1 X
Tr(vi (A)vi (A)) =
|?i (v)| = ki .
n
n v?V (?)
The reader has already probably noted the similarities between the recurrence
relation (16) satisfied by the polynomials vi of both boundary graphs and distanceregular graphs. This will lead to a unified formula for both type of graphs, which is
the main result of this section. Before proceeding with our study, however, we must
recall some basic facts on orthogonal polynomials of a discrete variable. For more
details see, for instance, [12]. Let {pi } be a sequence of polynomials satisfying the
ANTIPODAL DISTANCE-REGULAR GRAPHS 133
following recurrence, initiated with p?1 = 0, p0 = 1:
xpi = bi?1 pi?1 + ai pi + ci+1 pi+1
where bi?1 , ai , ci+1 are real numbers such that ci+1 =
/ 0 and bi?1 ci+1 > 0, 1 ?
i ? d. Then, the following orthogonality property holds:
d
X
pi (xl )pj (xl )?l = ?ij ki ,
(0 ? i, j < d + 1)
(21)
l=0
where the points xl are the (real and different) roots of pd+1 , k0 is any given positive
number, ki = bi?1
ci ki?1 , 1 ? i ? d, and
d
X
1
p2i (xl )
?d
=
p0 (xl )pd (xl )
=
?l i=0 ki
?d+1 kd d+1
(22)
with ?i the leading coefficient of pi . Moreover, these polynomials satisfy also the
so-called dual orthogonality property:
d
X
i=0
pi (xl )pi (xm )
1
1
= ?lm ,
ki
?l
(0 ? l, m < d + 1).
(23)
The polynomials p?l ? Rd [x] defined on the mesh M = {x0 , . . . , xd } by p?l (xi ) =
pi (xl ) are called the dual polynomials of the {pi }.
Let us see some consequences of these results for boundary graphs and distanceregular graphs.
Theorem 3.2.
Let ? be a distance-regular graph or a boundary graph on n
vertices, with eigenvalues ?0 = ? > ?1 > и и и > ?d , and let vd be the polynomial
of degree d of the corresponding sequence of orthogonal polynomials. Then,
d
X
1
vi2 (?l )
хl vd (?l )
,
= kvl? k2 =
=n
?l
ki
х0 vd (?)
i=0
where хl = х0 (?l ), х(x) = vd+1 (x) =
Qd
l=0 (x
(24)
? ?l ).
Proof. We have seen that, in both cases, the polynomials vi satisfy a recurrence
relation of the type
xvi = bi?1 vi?1 + ai vi + ci+1 vi+1
(25)
with v?1 = 0, v0 = 1, and c1 , . . . , cd , a0 , . . . , ad , b0 , . . . , bd?1 being constants
satisfying ai = ? ? bi ? ci (cd+1 =
/ 0 and b?1 can be conveniently chosen). We
have also seen that they satisfy an orthogonal property:
d
X
l=0
vi (?l )vj (?l )?l = ?ij ki
(26)
134 JOURNAL OF GRAPH THEORY
n
with k0 = 1 and ki = bi?1
ci ki?1 , 1 ? i ? d. Then, by applying (22) with ?d = х0
(the leading coefficient of the Hoffman polynomial) and vd+1 (x) = х(x), we get
kvi? k2 =
d
X
vi2 (?l )
i=0
ki
=n
хl vd (?l )
.
х0 kd
(27)
Hence, it suffices to show that kd = kvd k2 = vd (?). By induction, k?1 = 0 =
v?1 (?) (by convention), and k0 = 1 = v0 (?). Let us then assume that the result
holds for ki?1 and ki . Evaluating (25) at ? and solving for vi+1 (?), we obtain
vi+1 (?) =
(? ? ai )ki ? bi?1 ki?1
bi
=
ki = ki+1 ,
ci+1
ci+1
where we have used that bi?1 ki?1 = ci ki and ai = ? ? bi ? ci .
In particular, we can obtain the following known result for the multiplicities of
a distance-regular graph (see Bannai and Ito [1]):
Corollary 3.3.
Let ? be a distance-regular graph with eigenvalues ?0 = k >
?1 > и и и > ?d , and let vd the d-distance polynomial. Then,
m(?l ) =
х0 vd (?)
хl vd (?l )
(0 ? l ? d)
(28)
l)
Proof. From (20), we have ?l = m(?
n . Then the result follows from (24).
By (28) note that, since х0 vd (?) = х0 kd > 0, we must also have хl vd (?l ) > 0.
n
= kvi? k2 , that is,
Moreover, we also have m(?
i)
m(?i ) =
n
hu(?i ), v(?i )i
(0 ? i ? d)
(29)
which corresponds to the formula given by Biggs [2, Th.21.4] for the multiplicities of the eigenvalues of ?. In this formula, v(?i ) = (v0 (?i ), . . . , vd (?i ))T and
u(?i ) = ( k10 v0 (?i ), . . . , k1d vd (?i )) are respectively the right and left eigenvalues of
B , corresponding to the eigenvalue ?i , and with first component 1. For any i =
/ j,
the vectors v(?i ) and u(?j ) are orthogonal.
With respect to the consequences of Theorem 3.2 for boundary graphs, we have
the following result.
Corollary 3.4.
?d . Then,
Let ? be a boundary graph with eigenvalues ?0 > ?1 > и и и >
d
X
vi2 (?l )
i=0
ki
=
n?l
.
?0
(30)
Proof. Now, vd is the polynomial of Rd [x] defined by vd (?l ) = (?1)l , 0 ?
l ? d (the Hoffman polynomial minus the alternating polynomial), so that ?d =
ANTIPODAL DISTANCE-REGULAR GRAPHS 135
Pd
0
= ?n0 . Then, applying (24) with vd+1
(?l )vd (?l ) = хl (?1)l = ?l , and
= 1, the result follows. Alternatively, the comparison between (18) and
(26) gives ?l = ??l0n , so that (30) is just ?1l .
We have already seen that, in the case of distance-regular graphs, the value of ki
corresponds to the number of vertices |?i (v)| for any v . But, clearly, such a value
is also the sum of the entries of every row or column of vi (A). The following result
shows that this last property is also shared by boundary graphs.
1
l=0 ?l
kd = k0
Lemma 3.5.
Let A be the adjacency matrix of a distance-regular graph or
a boundary graph, and let {vi , 0 ? i ? d} be the corresponding sequence of
orthogonal polynomials. Then, the sum of the entries of each row or column of
vi (A) is ki .
Proof. Using previous results, we have:
hvi ei , ji = hei , vi ji = hei , vi (?)ji = vi (?) = ki .
4. EXTREMAL BOUNDARY GRAPHS AND
DISTANCE-REGULAR GRAPHS
We devote this last section to study the relationship between extremal boundary
graphs and distance-regular graphs. First, we recall that a graph ? is antipodal
when the relation ei ? ej iff ei = ej or ?(ei , ej ) = D(?) is an equivalence relation. In particular, ? is 2-antipodal when all equivalence classes have 2 elements.
Alternatively, ? is 2-antipodal when every connected component of ?D(?) is K2 .
In [8], as a consequence of a more general result about r-antipodal graphs, it was
proved the following result:
Lemma 4.1.
graphs.
All 2-antipodal distance-regular graphs are extremal boundary
This section is mainly devoted to examine the additional conditions under which
the reciprocal statement holds. We begin by studying the structure of the graph as
??seen from a diametral vertex.?? Notice that, to say that e is a diametral vertex of an
extremal boundary graph ? is equivalent to saying that ?d (e) consists of just one
vertex (e?). We will use again the results on orthogonal polynomials of Section 2.
Lemma 4.2.
Let ? be a boundary graph with a pair of conjugate vertices e, e?.
Then, for k = ?1, 0, . . . , d,
wk e + wd?1?k e? = j.
Proof. For k = ?1 and k = d the result is straightforward. Then, let us consider the remaining cases k = 0, 1, . . . , d?1. By using the spectral decompositions
136 JOURNAL OF GRAPH THEORY
of e and e?:
e=
d
X
1
zl,
j+
n
l=1
e? =
d
X
1
(?1)l z l ,
j+
n
l=1
with z l ? Ker (A ? ?l I),
we get
wk e + wd?1?k e? =
d
X
wk (?)
wd?1?k (?)
j+
j
wk (?l )z l +
n
n
l=1
+
d
X
(?1)l (T ? wk )(?l )z l
l=1
1
= (wk (?) + wd?1?k (?))j
n
+
d
X
(wk (?l ) + (?1)l (?1)l+1 wk (?l ))z l = j
l=1
as claimed.
Notice that, for k = 0, Lemma 4.2 corresponds to (10) in Section 2.
Let ? be a boundary graph with a pair of conjugate vertices e, e?. From Lemma
4.2 we have, for any vertex v ? V (?),
hwk e, vi + hwd?1?k e?, vi = 1.
(31)
We are now ready to present the main result of this section.
Theorem 4.3.
An extremal boundary graph ? is distance-regular 2-antipodal
around any diametral vertex e, and the corresponding local intersection array is
independent of such a vertex.
Proof. Let k = 0, 1, . . . , d and v ? ?k (e). Then, hwk e, vi = ?k hAk e, vi, and
hwd?1?k e?, vi = 0 since ?(v, e?) ? d ? k . From (31) we obtain,
hAk e, vi =
1
?k
(32)
for any v ? ?k (e). Now, let k = ?1, 0, . . . , d ? 1 and v ? ?k+1 (e). Then,
hwk e, vi = 0, and hwd?1?k e?, vi = ?d?1?k hAd?1?k e?, vi, because ?(v, e?) ?
d ? k ? 1. Applying again (31) we have
hAd?1?k e?, vi =
1
?d?1?k
(33)
for any v ? ?k+1 (e).
For a given vertex v ? ?k (e), 0 ? k ? d, let ak (v), bk (v), and ck (v) denote
the number of vertices adjacent to v and belonging to ?k (e), ?k+1 (e), and ?k?1 (e)
respectively. Then, for any k , we clearly have ak (v) + bk (v) + ck (v) = ?, where
ANTIPODAL DISTANCE-REGULAR GRAPHS 137
a0 (v) = ad (v) = 0, b0 (v) = cd (v) = ? and, by convention, c0 (v) = 0 and
bd (v) = 0.
Denoting by u1 , . . . , uck (v) the vertices of ?k?1 (e) which are adjacent to v ,
equation (32) yields:
ck (v)
X
1
ck (v)
k
= hA e, vi =
hAk?1 e, ul i =
.
?k
?k?1
l=1
(34)
Similarly, if w1 , . . . , wbk (v) represent the vertices in ?k+1 (e) which are adjacent to
v , equation (33) leads to
1
?d?k
= hA
d?k
e?, vi =
bk (v)
X
hAd?k?1 e?, wl i =
l=1
bk (v)
.
?d?1?k
(35)
As a consequence of (34) and (35) notice, in particular, that the numbers bk =
bk (v) and ck = ck (v) do not depend on the considered vertex v ? ?k (e). Moreover,
bk =
?d?1?k
,
?d?k
ck =
?k?1
,
?k
ak = ? ? bk ? ck ,
(36)
are also independent of the chosen diametral vertex e.
From Theorem 4.3 and Corollary 4.1 we reach the following characterization of
those extremal boundary graphs all of whose vertices are diametral.
Theorem 4.4.
A graph ? is distance-regular 2-antipodal if and only if it is a
diametral extremal boundary graph.
By (29) and (30), an immediate consequence of this characterization is:
Proposition 4.5.
The multiplicities of the eigenvalues of a distance-regular 2antipodal graph (diametral extremal boundary graph) are given by
m(?i ) =
?0
?i
(i = 0, 1, . . . , d).
Reasoning as in (32) we get that, for any diametral vertex e of an extremal
boundary graph, hwi e, vi = 1 if and only if ?(v, e) ? i. Hence, the polynomials
vi = wi ? wi?1 satisfy the following result.
Corollary 4.6. Let e be a diametral vertex of an extremal boundary graph. Then,
for any 1 ? j ? n, the vector vi e has j th component equal to 1 if ?(e, ej ) = i,
and 0 otherwise.
So, we could say that vi , 0 ? i ? d, is the ??locally?? i-distance polynomial of
the graph.
We end the section by giving some more results on (general) extremal boundary
graphs. To begin with, note that, given a diametral vertex e of ?, the numbers
138 JOURNAL OF GRAPH THEORY
ki defined by k0 = 1 and bi?1 ki?1 = ci ki (i = 1, . . . , d) correspond now to
ki = |?i (e)|. Then, we have bi?1 ki?1 + ai ki + ci+1 ki+1 = ?ki and the tridiagonal
matrix B of Section 2 has the eigenvector (k0 , k1 , . . . , kd )T with corresponding
eigenvalue ?. Since k0 = v0 (?) = 1, we have ki = vi (?) (i = 0, 1, . . . , d), as we
already know. Hence, (18) yields the following result:
Proposition 4.7.
Then,
Let e be a diametral vertex of an extremal boundary graph.
|?i (e)| = vi (?) =
?0
kvi k2 .
n
From previous results, the local intersection array of an extremal boundary graph
(and hence the intersection array of a distance-regular 2-antipodal graph) is determined by its eigenvalues. Indeed, from the equalities
(T ? wk )(?i ) = wd?1?k (?i )
(1 ? i ? d),
wk (?) + wd?1?k (?) = n,
we get a linear system of equations with the coefficients of wk and wd?1?k as
unknowns. Then, Cramer's rule yields:
?d?1?k = (?1)k+1
Hk (?1 , . . . , ?d )
n
Hk (?, ?1 , . . . , ?d )
(0 ? k ? d ? 2)
where Hk (x1 , . . . , xm ) stands for the determinant of order m
1
1
1
..
.
1
x1
x2
x3
..
.
xm
x21
x22
x23
..
.
x2m
и и и xk1
1
x1
x21
k
и и и x2
?1
?x2
?x22
k
и и и x3
1
x3
x23
..
..
..
..
.
.
.
.
и и и xkm (?1)m+ 1 (?1)m+ 1 xm (?1)m+ 1 x2m
?k
xm?2
1
m?2 ?k
?x2
?k
xm?2
3
..
.
иии
?k
и и и (?1)m+ 1 xm?2
m
иии
иии
иии
By (34) and (35) we get bk = cd?k , and an explicit formula for such coefficients,
as stated in the next Corollary.
Corollary 4.8. The entries of the local intersection array of an extremal boundary graph ? are univocally determined by their eigenvalues, ? > ?1 > и и и > ?d ,
through the formulas:
bk = cd?k = ?
Hk (?1 , . . . , ?d )Hk?1 (?, ?1 , . . . , ?d )
Hk (?, ?1 , . . . , ?d )Hk?1 (?1 , . . . , ?d )
b0 = cd = ?,
bd?1 = c1 = 1,
(1 ? k ? d ? 2)
ak = ? ? bk ? ck .
Keeping in mind our description of an extremal boundary graph as a local
distance-regular 2-antipodal graph, we come back to the subgraph ?? induced by
the conjugate vertices. Then,
ANTIPODAL DISTANCE-REGULAR GRAPHS 139
Proposition 4.9. Let ? be an extremal boundary graph with 1 + ?1 + и и и + ?d <
0. Then, either every vertex of each connected component of ?? is diametral, or
neither is.
Proof. Let e be a diametral vertex of ?, and let ei be a conjugate vertex adjacent
to e. Let e? and e?i be their respective conjugate vertices which are also adjacent
vertices by Proposition 1.1. Therefore, ?(ei , e?i ) ? d ? 2.
Moreover, in [8] it was shown that the first two terms of the alternating polynomial of an extremal boundary graph (d ? 2) are:
P =?
n d?1
[x
? (1 + ?1 + и и и + ?d )xd?2 + и и и].
?0
Hence, we have
hP ei , e?i i = ?
n
(hAd?1 ei , e?i i ? (1 + ?1 + и и и + ?d )hAd?2 ei , e?i i) = 0
?0
so that ?(ei , e?i ) = d and ei is also diametral.
There are boundary graphs with self-conjugate vertices, but the examples of
extremal boundary graphs known by the authors [8] have no such vertices. In the
way of studying their possible existence, it could be worth considering the following
facts:
(1) If d is odd such vertices cannot exist. Indeed, By Proposition 1.1 and the
property of being locally distance-regular, a self-conjugate vertex e would be
on a diametral path, and at the same distance of its end vertices, but this only
can happen if d is even.
(2) Assuming that d is even, say d = 2d0 , Lemma 4.2 with k = d0 and for a
self-conjugate vertex e yields: wd0 e + wd0 ?1 e = j . Therefore, the graph has
radius d0 , the self-conjugate vertices are in the center of the graph, and ?d0 (e)
contains all the pairs of diametral vertices.
References
[1]
[2]
[3]
[4]
[5]
E. Bannai and T. Ito, Algebraic combinatorics I: Association schemes,
Benjamin-Cummings Lecture Note Ser. 58, London (1993).
N. Biggs, Algebraic graph theory, Cambridge University Press, Cambridge
(1993).
A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance regular graphs,
Springer-Verlag (1989).
F. R. K. Chung, Diameter and eigenvalues, J. Amer. Math. Soc. 2 (2) (1989),
187?196.
F. R. K. Chung, V. Faber, and T. H. Manteuffel, An upper bound on the
diameter of a graph from eigenvalues associated with its laplacian. SIAM J.
Disc. Math. 7 (3) (1994), 443?457.
140 JOURNAL OF GRAPH THEORY
[6]
[7]
[8]
[9]
[10]
[11]
[12]
C. Delorme and P. Sole?, Diameter, covering index, covering radius and eigenvalues. European J. Combin. 12 (1991), 95?108.
M. A. Fiol, E. Garriga, and J. L. A. Yebra, On a class of polynomials and its
relation with the spectra and diameters of graphs. J. Combin. Theory Ser. B
67 (1996), 48?61.
M. A. Fiol, E. Garriga, and J. L. A. Yebra, Boundary graphs: The limit case
of a spectral property (I), submitted, 1995.
M. A. Fiol, E. Garriga, and J. L. A. Yebra, Boundary graphs: The limit case
of a spectral property (II). Discrete Math., to appear.
A. J. Hoffman, On the polinomial of a graph. Amer. Math. Monthly 70 (1963),
30?36.
B. Mohar, Eigenvalues, diameter and mean distance in graphs. Graphs Combin. 7 (1991), 53?64.
A. F. Nikiforov, S. K. Suslov, and V. B. Uvarov, Classical orthogonal polynomials of a discrete variable, Springer-Verlag, Berlin (1991).
Документ
Категория
Без категории
Просмотров
2
Размер файла
383 Кб
Теги
352
1/--страниц
Пожаловаться на содержимое документа