David Joyner

On quadratic residue codes and hyperelliptic curves

For an odd prime p and each non-empty subset S ⊂ GF (p), consider the hyperelliptic curve XS defined by y 2 = fS(x), where fS(x) = Q a∈S (xa). Using a connection between binary quadratic residue codes and hyperelliptic curves over GF (p), this paper investigates how coding theory bounds give rise to bounds such as the following example: for all sufficiently large primes p there exists a subset S ⊂ GF (p) for which the bound |XS(GF (p))| > 1.39p holds. We also use the quasi-quadratic residue codes defined below to construct an example of a formally self-dual optimal code whose zeta function does not satisfy the "Riemann hypothesis." Keywords: binary linear codes, hyperelliptic curves over a finite field, quadratic residue codes, (11T71, 11T24, 14G50, 94B40, 94B27) (i) This code is defined in §2 below. (ii) This overly simplistic definition brings to mind the famous Felix Klein quote: "Everyone knows what a curve is, until he has studied enough mathematics to become confused through the countless number of possible exceptions." Please see Tsafsman-Vladut [TV] or Schmidt [Sc] for a rigorous treatment. (iii) These codes will be defined in §4 below.

A long standing problem has been to develop "good" binary linear codes to be used for error-correction. This paper investigates in some detail an attack on this problem using a connection between quadratic residue codes and hyperelliptic curves. Codes with this kind of relationship have been investigated in Helleseth [H], Bazzi-Mitter [BM], Voloch [V1], and Helleseth-Voloch [HV]. This rest of this introduction is devoted to explaining in more detail the ideas discussed in later sections.

Let F = GF (2) be the field with two elements and C ⊂ F n denote a binary block code of length n. For any two x, y ∈ F n , let d(x, y) denote the Hamming metric:

d(x, y) = |{1 ≤ i ≤ n | x i = y i }|.
(1)

The weight wt(x) of x is the number of non-zero entries of x. The smallest weight of any non-zero codeword is denoted d -the minimum distance if C is linear. When C is linear, denote the dimension of C by k and call C an [n, k, d] 2 -code.

Denoting the volume of a Hamming sphere of radius r in F n by V (n, r), the binary version of the Gilbert-Varshamov bound asserts that (given n and d) there is an [n, k, d]

2 code C satisfying k ≥ log 2 ( 2 n
V (n,d-1) ) [HP].

Conjecture 1 (Goppa's conjecture [JV], [G]) The binary version of the Gilbert-Varshamov bound is asymptotically exact. For each odd prime p > 5, a QQR code (i) is a linear code of length 2p. Like the quadratic residue codes, the length and dimension are easy to determine but the minimum distance is more mysterious. In fact, the weight of each codeword can be explicitly computed in terms of the number of solutions in integers mod p to a certain type of ("hyperelliptic") polynomial equation. To explain the results better, some more notation is needed.

For our purposes, a hyperelliptic curve X over GF (p) is a polynomial equation of the form y 2 = h(x), where h(x) is a polynomial with coefficients in GF (p) with distinct roots (ii) . The number of solutions to y 2 = h(x) mod p, plus the number of "points at infinity" on X, will be denoted |X(GF (p))|. This quantity can be related to a sum of Legendre characters (see Proposition 1 below), thanks to classical work of Artin, Hasse, and Weil. This formula yields good estimates for |X(GF (p))| in many cases (especially when p is large compared to the degree of h). A long-standing problem has been to improve on the trivial estimate when p is small compared to the degree of h. It turns out the work of Tarnanen [T] easily yields some non-trivial information on this problem (see for example Lemma 3 below), but the results given here improve upon this.

For each non-empty subset S ⊂ GF (p), consider the hyperelliptic curve X S defined by y 2 = f S (x), where f S (x) = a∈S (x-a). Let B(c, p) be the statement: For all subsets S ⊂ GF (p), |X S (GF (p))| ≤ c • p holds. Note that B(2, p) is trivially true, so the statement B(2ǫ, p), for some fixed ǫ > 0, might not be horribly unreasonable.

Conjecture 2 ("Bazzi-Mitter conjecture" [BM]) There is a c ∈ (0, 2) such that, for an infinite number of primes p the statement B(c, p) holds.

It is remarkable that these two conjectures are related. In fact, using QQR codes we show that if, for an infinite number of primes p with p ≡ 1 (mod 4), B(1.77, p) holds then Goppa's conjecture is false. Although this is a new result, it turns out that it is an easy consequence of the QQR construction given in [BM] if you think about things in the right way. Using LQR codes (iii) we will remove the condition p ≡ 1 (mod 4) at a cost of slightly weakening the constant 1.77 (see Corollary 3).

The spectrum and Duursma zeta function of these QQR codes is discussed in Section 3 below and some examples are given (with the help of the software package SAGE [S]). We show that the analog of the Riemann hypothesis for the zeta function of an optimal formally self-dual code is false using the family of codes constructed in §2. The section ends with some intriguing conjectures.

We close this introduction with a few open questions which, on the basis of this result, seem natural.

Question 1 For each prime p > 5 is there an effectively computable subset S ⊂ GF (p) such that |X S (GF (p))| is "large"?

Here "large" is left vague but what is intended is some quantity which is unusual. By Weil's estimate (valid for "small"-sized subsets S), we could expect about p points to belong to |X S (GF (p))|. Thus "large" could mean, say, > c • p, for some fixed c > 1.

The next question is a strong version of the Bazzi-Mitter conjecture.

Question 2 Does there exist a c < 2 such that, for all sufficiently large p and all S ⊂ GF (p), we have

|X S (GF (p))| < c • p?
In the direction of these questions, a coding theory bound of McEliese-Rumsey-Rodemich-Welsh allows one to establish the following result (see Theorem 3): There exists a constant p 0 having the following property: if p ≡ 1 (mod 4) and p > p 0 then there exists a subset S ⊂ GF (p) for which the bound |X S (GF (p))| > 1.62p holds (iv) . Unfortunately, the method of proof gives no clue how to compute p 0 or S. Using the theory of long quadratic-residue codes, we prove the following lower bound (Theorem 6): For all p > p 0 there exists a subset S ⊂ GF (p) for which the bound |X S (GF (p))| > 1.39p holds. Again, we do not know what p 0 or S is.

Finally, Felipe Voloch [V2] has kindly allowed the author to include some interesting explicit constructions (which do not use any theory of error-correcting codes) in this paper (see §5 below). First, he shows the following result: If p ≡ 1 (mod 8) then there exists an effectively computable subset S ⊂ GF (p) for which the bound |X S (GF (p))| > 1.5p holds. A similar result holds for p ≡ 3, 7 (mod 8). Second, he gives a construction which answers Question 2 in the negative.

Cyclotomic arithmetic mod 2

Let R = F[x]/(x p -1), and let r S ∈ R denote the polynomial

r S (x) = i∈S x i ,
where S ⊆ GF (p). By convention, if S = ∅ is the empty set, r S = 0. We define the weight of r S , denoted wt(r S ), to be the cardinality |S|. (In other words, identify in the obvious way each r S with an element of F p and define the weight of r S to be the Hamming weight of the associated vector.). For the set Q of quadratic residues in GF (p) × and the set N of non-quadratic residues in GF (p) × , we have wt(r Q ) = wt(r N ) = (p -1)/2. Note that r 2 S = r 2S , where 2S is the set of elements 2s ∈ GF (p), for s ∈ S. Using this fact and the quadratic reciprocity law, one can easily show that the following are equivalent:

• r 2 Q = r Q , • 2 ∈ Q • p ≡ ±1 (mod 8). Moreover, if 2 ∈ N then r 2 Q = r N . Let S, S 1 , S 2 , S ′
1 denote subsets of GF (p), with S 1 ∩ S ′ 1 = ∅, and let S c = GF (p) -S denote the complement. For a ∈ GF (p), let

H(S 1 , S 2 , a) = {(s 1 , s 2 ) ∈ S 1 × S 2 | s 1 + s 2 ≡ a (mod p)}.
In particular,

• H(S 1 , S 2 , a) = H(S 2 , S 1 , a), (iv) Moreover, we can remove the hypothesis p ≡ 1 (mod 4) if we assume Conjecture 3.

• there is a natural bijection H(GF (p), S, a) ∼ = S,

• if S 1 ∩ S ′ 1 = ∅ then H(S 1 , S 2 , a) + H(S ′ 1 , S 2 , a) = H(S 1 + S ′ 1 , S 2 , a). Let h(S 1 , S 2 , a) = |H(S 1 , S 2 , a)| (mod 2). Adding |H(S 1 , S 2 , a)| + |H(S c 1 , S 2 , a)| = |S 2 | to |H(S c 1 , S c 2 , a)| + |H(S c 1 , S 2 , a)| = |S c 1 |, we obtain h(S 1 , S 2 , a) ≡ h(S c 1 , S c 2 , a) + |S c 1 | + |S 2 | (mod 2). (2)
From the definition of r S ,

r S1 (x)r S2 (x) = a∈GF (p) h(S 1 , S 2 , a)x a
in the ring R. Let * : R → R denote the involution defined by (r S ) * = r S c = r S + r GF (p) . We shall see below that this is not an algebra involution.

Lemma 1 For all S 1 , S 2 ⊂ GF (p), we have

• |S 1 | odd, |S 2 | even: r S1 r S2 = r * S1 r * S2 has even weight. • |S 1 | even, |S 2 | even: (r S1 r S2 ) * = r * S1 r * S2 has even weight. • |S 1 | even, |S 2 | odd: r S1 r S2 = r * S1 r * S2 has even weight. • |S 1 | odd, |S 2 | odd: (r S1 r S2 ) * = r * S1 r * S2 has odd weight.
This lemma follows from the discussion above by a straightforward argument. Note that R even = {r S | |S| even}, is a subring of R and, by the previous lemma, * is an algebra involution on R even .

QQR Codes

These are some observations on the interesting paper by Bazzi and Mitter [BM]. We shall need to remove the assumption p ≡ 3 (mod 8) (which they make in their paper) below.

If S ⊆ GF (p), let f S (x) = a∈S (x -a) ∈ GF (p)[x]. Let χ = ( p ) be the quadratic residue character, which is 1 on the quadratic residues Q ⊂ GF (p) × , -1 on the quadratic non-residues N ⊂ GF (p) × , and is 0 at 0 ∈ GF (p). Define C N Q = {(r N r S , r Q r S ) | S ⊆ GF (p)},
where N, Q are as above. (We identify in the obvious way each pair (r N r S , r Q r S ) with an element of F 2p . In particular, when S is the empty set, (r N r S , r Q r S ) is associated with the the zero vector in F 2p .)

We call this a QQR code (or a quasi-quadratic residue code). These are binary linear codes of length 2p and dimension

k = p, if p ≡ 3 (mod 4), p -1, if p ≡ 1 (mod 4).
This code has no codewords of odd weight, for parity reasons, by Lemma 1.

Remark 1 If p ≡ ±1 (mod 8) then C N Q "contains" a binary quadratic residue code. For such primes p, the minimum distance satisfies the well-known square-root lower bound, d ≥ √ p.

Based on computations using SAGE, the following statement is likely to be true.

Conjecture 3 For p ≡ 1 (mod 4), the associated QQR code and its dual satisfy:

C N Q ⊕ C ⊥ N Q = F 2p
, where ⊕ stands for the direct product (so, in particular,

C N Q ∩ C ⊥ N Q = {0}). If p ≡ 3 (mod 4) then the associated QQR code is self-dual: C ⊥ N Q = C N Q .
The self-dual binary codes have useful upper bounds on their minimum distance (for example, the Sloane-Mallows bound Theorem 9.3.5 in [HP]). Combining this with the lower bound mentioned above, we have the following result.

Lemma 2 Assume Conjecture 3. If p ≡ 3 (mod 4) then d ≤ 4 • [p/12] + 6. If p ≡ -1 (mod 8) then √ p ≤ d ≤ 4 • [p/12] + 6.
Note that these upper bounds (in the cases they are valid) are better than the asymptotic bounds of McEliese-Rumsey-Rodemich-Welsh for rate 1/2 codes.

Example 1 The following computations were done with the help of SAGE. When p = 5, C N Q has weight distribution [1, 0, 0, 0, 5, 0, 10, 0, 0, 0, 0].

When p = 7, C N Q has weight distribution
[1, 0, 0, 0, 14, 0, 49, 0, 49, 0, 14, 0, 0, 0, 1].

When p = 11, C N Q has weight distribution
[1, 0, 0, 0, 0, 0, 77, 0, 330, 0, 616, 0, 616, 0, 330, 0, 77, 0, 0, 0, 0, 0, 1].

When p = 13, C N Q has weight distribution
[1, 0, 0, 0, 0, 0, 0, 0, 273, 0, 598, 0, 1105, 0, 1300, 0, 598, 0, 182, 0, 39, 0, 0, 0, 0, 0, 0].

The following well-known result (v) shall be used to estimate the weights of codewords of QQR codes.

Proposition 1 (Artin, Hasse, Weil) Assume S ⊂ GF (p) is non-empty.

(v) See for example Weil [W] or Schmidt [Sc], Lemma 2.11.2.

• |S| even:

a∈GF (p) χ(f S (a)) = -p -2 + |X S (GF (p))|.
• |S| odd:

a∈GF (p) χ(f S (a)) = -p -1 + |X S (GF (p))|.
• |S| odd: The genus of the (smooth projective model of the) curve

y 2 = f S (x) is g = |S|-1 2 and a∈GF (p) χ(f S (a)) ≤ (|S| -1)p 1/2 + 1.
• |S| even: The genus of the (smooth projective model of the) curve

y 2 = f S (x) is g = |S|-2 2 and a∈GF (p) χ(f S (a)) ≤ (|S| -2)p 1/2 + 1.
Obviously, the last two estimates are only non-trivial for S "small" (e.g., |S| < p 1/2 ).

Lemma 3 (Tarnanen [T], Theorem 1) Fix τ , 0.39 < τ < 1. For all sufficiently large p, the following statement is false: For all subsets S ⊂ GF (p) with |S| ≤ τ p, we have 0.42p

< |X S (GF (p))| < 1.42p.
Remark 2 (1) Here the meaning of "sufficiently large" is hard to make precise. The results of Tarnanen are actually asymptotic (as p → ∞), so we can simply say that the negation of part (1) of this Lemma contradicts Theorem 1 in [T].

(2) This Lemma does not seem to imply "B(1.42, p) is false, for sufficiently large p" (so Theorem 6 below is a new result), though it would if the condition 0.42p < |X S (GF (p))| could be eliminated. Also of interest is the statement about character sums in Theorem 1 of Stepanov [St].

Proof: This is an immediate consequence of the Proposition above and Theorem 1 in [T]. ✷ Lemma 4 (Bazzi-Mitter [BM], Proposition 3.3) Assume 2 and -1 are quadratic non-residues mod p (i.e. p ≡ 3 (mod 8)).

If c = (r N r S , r Q r S )
is a nonzero codeword of the [2p, p] binary code C N Q then the weight of this codeword can be expressed in terms of a character sum as

wt(c) = p - a∈GF (p) χ(f S (a)), if |S| is even, and wt(c) = p + a∈GF (p) χ(f S c (a)), if |S| is odd.
In fact, looking carefully at their proof, one finds the following result.

Proposition 2 Let c = (r N r S , r Q r S ) be a nonzero codeword of C N Q . (a) If |S| is even wt(c) = p - a∈GF (p) χ(f S (a)) = 2p + 2 -|X S (GF (p))|.
(b) If |S| is odd and p ≡ 1 (mod 4) then the weight is

wt(c) = p - a∈GF (p) χ(f S c (a)) = 2p + 2 -|X S c (GF (p))|. (c) If |S| is odd and p ≡ 3 (mod 4) then wt(c) = p + a∈GF (p) χ(f S c (a)) = |X S c (GF (p))| -2. Proof: If A, B ⊆ GF (p) then the discussion in §1 implies wt(r A r B ) = k∈GF (p) parity |A ∩ (k -B)|, (3)
where k -B = {kb | b ∈ B} and parity(x) = 1 if x is an odd integer, and = 0 otherwise. Let S ⊆ GF (p), then we have

p -wt(r Q r S ) -wt(r N r S ) = a∈GF (p) 1 -parity |Q ∩ (a -S)| -parity |N ∩ (a -S)| . Let T a (S) = 1 -parity |Q ∩ (a -S)| -parity |N ∩ (a -S)|. Case 1. If |S| is even and a ∈ S then 0 ∈ a -S so |Q ∩ (a -S)| odd implies that |N ∩ (a -S)| is even, since 0 is not included in Q ∩ (a -S) or N ∩ (a -S). Likewise, |Q ∩ (a -S)| even implies that |N ∩ (a -S)| is odd. Therefore T a (S) = 0. Case 2. If |S| is even and a / ∈ S then parity |Q ∩ (a -S)| =parity|N ∩ (a -S)|. If |Q ∩ (a -S)| is even then T a (S) = 1 and if |Q ∩ (a -S)| is odd then T a (S) = -1. Case 3. |S| is odd. We claim that (a -S) c = a -S c . (Proof: Let s ∈ S and s ∈ S c . Then a -s = a -s =⇒ s = s, which is obviously a contradiction. Therefore (a -S) ∩ (a -S c ) = ∅, so (a -S) c ⊇ (a -S c
). Replace S by S c to prove the claim.)

Also note that If |S| = 2 then a χ(f S (a)) can be computed explicitly (it is "usually" equal to -1 -see Proposition 1 in [Wa]). If |S| = 3 then a χ(f S (a)) can be expressed in terms of a hypergeometric function 2 F 1 over GF (p) (see Proposition 2 in [Wa]).

Q ∩ (a -S) ⊔ Q ∩ (a -S c ) = GF (p) ∩ Q = Q has |Q| = p-
It has already been observed that the following fact is true. Since its proof using basic facts about hyperelliptic curves is so short, it is included here.

Corollary 1 C N Q is an even weight code.

Proof: Since p is odd 1 = -1 in GF (p), so every affine point in X S (GF (p)) occurs as an element of a pair of solutions of y 2 = f S (x). There are two points at infinity (if ramified, it is counted with multiplicity two), so in general |X S (GF (p))| is even. The formulas for the weight of a codeword in the above Proposition imply every codeword has even weight. ✷

As a consequence of this Proposition and Lemma 2, we have the following result. If p = 11 and S = {1, 2, 3, 4} then (r S (x)r N (x), r S (x)r Q (x)) = (x 10 + x 9 + x 7 + x 6 + x 5 + x 4 + x 2 + 1, x 10 + x 9 + x 7 + x 6 + x 5 + x 3 + x + 1), corresponds to the codeword (1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1) of weight 16. An explicit computation shows that the character sum a∈GF (11) χ(f S (a)) is -5, as expected.

If p = 11 and S = {1, 2, 3} then

(r S (x)r N (x), r S (x)r Q (x)) = (x 9 + x 7 + x 5 + x 4 + x 3 + x 2 + x, x 10 + x 8 + x 6 + x 3 + x 2 + x + 1).
corresponds to the codeword (0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1) of weight 14. An explicit computation shows that the character sum a∈GF (11) χ(f S c (a)) is 3, as predicted.

Recall B(c, p) is the statement:

|X S (GF (p))| ≤ c • p for all S ⊂ GF (p).
Theorem 1 (Bazzi-Mitter) Fix c ∈ (0, 2). If B(c, p) holds for infinitely many p with p ≡ 1 (mod 4) then there exists an infinite family of binary codes with asymptotic rate R = 1/2 and relative distance δ ≥ 1 -c 2 . This is an easy consequence of the above Proposition and is essentially in [BM] (though they assume p ≡ 3 (mod 8)).

Theorem 2 If B(1.77, p) is true for infinitely many primes p with p ≡ 1 (mod 4) then Goppa's conjecture is false.

Proof: Recall Goppa's conjecture is that the binary asymptotic Gilbert-Varshamov bound is best possible for any family of binary codes. The asymptotic GV bound states that the rate R is greater than or equal to 1 -H 2 (δ), where

H q (δ) = δ • log q (q -1) -δ log q (δ) -(1 -δ) log q (1 -δ)
is the entropy function (for a q-ary channel). Therefore, according to Goppa's conjecture, if R = 1 2 (and q = 2) then the best possible δ is δ 0 = .11. Assume p ≡ 1 (mod 4). Goppa's conjecture implies that the minimum distance of our QQR code with rate R = 1 2 satisfies d < δ 0 • 2p = .22p, for sufficiently large p. Recall that the weight of a codeword in this QQR code is given by Proposition 2. B(1.77, p) (with p ≡ 1 (mod 4)) implies (for all S ⊂ GF (p)) wt((r S r N , r S r Q )) ≥ 2p -|X S (GF (p))| ≥ 0.23p. In other words, for p ≡ 1 (mod 4), all nonzero codewords have weight at least 0.23p. This contradicts the estimate above. ✷

Using the same argument and the first McEliese-Rumsey-Rodemich-Welsh (MRRW) bound ([HP], Theorem 2.10.6), we prove the following unconditional result.

Theorem 3 For all sufficiently large primes p for which p ≡ 1 (mod 4), the statement B(1.62, p) is false.

Proof: If a prime p satisfies B(1.62, p) then we shall call it "admissible." We show that the statement "B(1.62, p) holds for all sufficiently large primes p for which p ≡ 1 (mod 4)" contradicts the first asymptotic MRRW bound. Indeed, this MRRW bound states that the rate R is less than or equal to

h(δ) = H 2 ( 1 2 -δ(1 -δ)).
This, and the fact that R = 1 2 for our QQR codes (with p ≡ 1 (mod 4)), imply δ ≤ δ 0 = h -1 (1/2) ∼ = 0.187. Therefore, for all large p (admissible or not), d ≤ δ 0 • 2p. On the other hand, if p is admissible and This is of course the same as the above theorem, except that we have used Corollary 2 (which unfortunately depends on Conjecture 3) to remove the hypothesis p ≡ 1 (mod 4).

|X S (GF (p))| ≤ c • p (where c = 1.62) then by the above argument, d ≥ 2 • (p -c 2 p). Together, we obtain 1 -c 2 ≤ δ 0 , so c ≥ 2 • (1 -h -1 (1/2)) ∼ = 1.626.

Weight distributions

In [D1] Iwan Duursma associates to a linear code C over GF (q) a zeta function Z = Z C of the form

Z(T ) = P (T ) (1 -T )(1 -qT )
,

where

ξ C ⊥ (s) = ξ C (1 -s).
Abusing terminology, we call both Z C and ζ C a Duursma zeta function. In fact, if ρ i denotes the i-th zero of the zeta function Z(T ) of an actual code then equations ( 5)-( 6) of [D2] implies (for the even weight binary codes we are considering here) the relation

d = 2 - i ρ -1 i .
Therefore, further knowledge of the zeros of Z(T ) could be very useful. If C is self-dual (or actually only formally self-dual) then the zeros of the ζ-function occur in pairs about the "critical line" Re(s) = 1 2 . Following Duursma, we say (for formally self-dual codes C) the zeta function ζ C satisfies the Riemann hypothesis if all its zeros occur on the "critical line".

Example 3

The following computations were done with the help of SAGE. If p = 7 then the [14,7,4 It would be interesting to know if the Duursma zeta function Z(T ) of C N Q , for p ≡ 3 (mod 4), always satisfies the Riemann hypothesis.

A self-dual code is called extremal if its minimum distance satisfies the Sloane-Mallows bound [D3] and optimal if its minimum distance is maximal among all such linear codes of that length and dimension (see also Chinen [Ch1], [START_REF]An abundance of invariant polynomials satisfying the Riemann hypothesis[END_REF]). As noted above, the Duursma zeta function only depends on the weight enumerator. It has been conjectured that, for all extremal self-dual codes C, the ζ-function satisfies the Riemann hypothesis. The example below shows that "extremal self-dual" cannot be replaced by "optimal formally self-dual".

Based on computer computations using SAGE, the following statement appears to be true, though we have no proof.

Conjecture 4 If p ≡ 1 (mod 4) then the code C ′ spanned by C N Q and the all ones codeword (i.e., the smallest code containing C N Q and all its complementary codewords) is a formally self-dual code of dimension p.

Moreover, if A = [A 0 , A 1 , ..., A n ] denotes the weight distribution vector of C N Q then the weight distribution vector of C ′ is A + A * , where A * = [A n , ..., A 1 , A 0 ].
Using SAGE, it can be shown that the Riemann hypothesis is not valid for these "extended QQR codes" in general, as the following example illustrates.

Example 4 If p = 13 then C ′ is a [26,13,6] code with weight distribution [1,0,0,0,0,0,39,0,455,0,1196,0,2405,0,2405,0,1196,0,455,0,39,0,0,0,0,0,1]. This is (by coding theory tables, as included in SAGE) an optimal, formally self-dual code. This code C ′ has zeta polynomial P (T ) =

Long Quadratic Residue Codes

We now introduce a new code, constructed similarly to the QQR codes discussed above:

C = {(r N r S , r Q r S , r N r * S , r Q r * S ) | S ⊆ GF (p)}.
We call this a long quadratic residue code, or LQR code for short, and identify it with a subset of F 4p .

Observe that this code is non-linear. For any S ⊆ GF (p), let

c S = (r N r S , r Q r S , r N r * S , r Q r * S )
and let

v S = (r N r S , r Q r S , r N r S , r Q r S ).
If S 1 ∆S 2 denotes the symmetric difference between S 1 and S 2 then it is easy to check that

c S1 + c S2 = v S1∆S2 . (4)
We now compute the size of C using Lemma 1. We prove the claim: if p ≡ 3 (mod 4) then the map that sends S to the codeword c S is injective. This implies |C| = 2 p . Suppose not, then there are two subsets S 1 , S 2 ⊆ GF (p) that are mapped to the same codeword. Subtracting c S1 -

c S2 = c S1 + c S2 = v S1∆S2 , and the subset T = S 1 ∆S 2 satisfies r Q r T = r N r T = r Q r T c = r N r T c = 0. If |T | is even then 0 = (r Q + r N )r T = (r GF (p) -1)r T = r T .
This forces T to be the empty set, so S 1 = S 2 . Now if |T | is odd then similar reasoning implies that T c is the empty set. Therefore, S 1 = ∅ and S 2 = GF (p) or vice versa. This proves the claim.

In case p ≡ 1 (mod 4), we claim: |C| = 2 p-1 . Again, suppose there are two subsets S 1 , S 2 ⊆ GF (p) that are mapped to the same codeword. Then the subset

T = S 1 ∆S 2 satisfies r Q r T = r N r T = r Q r T c = r N r T c = 0. This implies either T = ∅ or T = GF (p). Therefore, either S 1 = S 2 or S 1 = S c
2 . Combining this discussion with Proposition 1, we have proven the following result.

Theorem 4 The code C has length n = 4p and has size M = 2 p-1 if p ≡ 1 (mod 4), and size M = 2 p if p ≡ 3 (mod 4). If p ≡ 3 (mod 4) then the minimum non-zero weight is 2p and the minimum distance is at least

d p = 4p -2 max S⊂GF (p) |X S (GF (p))|. If p ≡ 1 (mod 4) then C is a binary [4p, p -1, d p ]-code.
Remark 5 If p ≡ 3 (mod 4), there is no simple reason I can think of why the minimum distance should actually be less than the minimum non-zero weight.

Lemma 5 If p ≡ 1 (mod 4) then

• v S = c S , • c S1 + c S2 = c S1∆S2 , • the code C is isomorphic to the QQR code C N Q . if p ≡ 3 (mod 4) and |S| is even then wt (r N r S , r Q r S , r N r * S , r Q r * S ) = wt (r N r S , r Q r S ) + wt (r N r * S , r Q r * S ) = p -a∈GF (p) f S (a) p + p + a∈GF (p) f S (a) p = 2p, (6)
and if p ≡ 3 (mod 4) and |S| is odd then

wt (r N r S , r Q r S , r N r * S , r Q r * S ) = wt (r N r S , r Q r S ) + wt (r N r * S , r Q r * S ) = p + a∈GF (p) f S (a) p + p -a∈GF (p) f S (a) p = 2p. (7)

✷

Example 5

The following examples were computed with the help of SAGE. When p = 11 and S = {1, 2, 3, 4}, c S corresponds to the codeword (0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0) of weight 22. When p = 11 and S = {1, 2, 3}, c S corresponds to the codeword

(1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0) of weight 22.

It turns out Lemma 6 allows us to improve the statement of Theorem 2 in §2. The next subsection is devoted to this goal.

Goppa's conjecture revisited

We shall now remove the condition p ≡ 1 (mod 4) in one of the results in §2, at a cost of weakening the constant involved.

Assuming B(c, p) holds, we have that the minimum distance of C is ≥ min(d p , 2p) ≥ 4p(1 -c 2 ) and the information rate is R = 1 4 + 1 4p . When R = 1/4, Goppa's conjecture gives δ = 0.214... . So Goppa's conjecture will be false if 1 -c 2 = 0.215, or c = 1.57. We have the following improvement of Theorem 2.

Theorem 5 If the B(1.57, p) is true for infinitely many primes p then Goppa's conjecture is false.

A similar argument (using h(x) and the MRRW bound in place of 1 -H 2 (x) and the hypothetical Goppa bound) gives Theorem 6 B(1.39, p) cannot be true for infinitely many primes p. In other words, for all "sufficiently large" p, we must have X S (GF (p)) > 1.39p for some S ⊂ GF (p).

Some results of Voloch

Lemma 8 (Voloch) If p ≡ 1, 3 (mod 8) then |X Q (GF (p))| = 1.5p + a, where Q is the set of quadratic residues and a is a small constant, -1 2 ≤ a ≤ 5 2 . A similar bound holds if X Q is replaced by X N and p ≡ 1, 3 (mod 8) is replaced by p ≡ 7 (mod 8) (in which case 2 is a quadratic residue).

Proof: By Proposition 1, we know that if p ≡ 3 (mod 8) (so |Q| is odd):

a∈GF (p) χ(f Q (a)) = -p -1 + |X Q (GF (p))|.
Similarly, if p ≡ 1 (mod 8) (so |Q| is even): Here is an extension of the idea in the above proof. Fix an integer ℓ > 2. Assuming ℓ divides p -1, there are distinct ℓ-th roots r 1 = 1, r 2 , ..., r ℓ in GF (p) for which x p-1 -1 = ℓ i=1 (x p-1 ℓ r i ). Also, x p-1 ℓ -1 = a∈P ℓ (xa) = f P ℓ (x), where P ℓ denotes the set of non-zero ℓ-th powers in GF (p).

Claim: It is possible to find an infinite sequence of primes p satisfying p ≡ 1 (mod ℓ) and χ(r i -1) = 1, for all 2 ≤ i ≤ ℓ (where χ denotes the Legendre character mod p). If the claim is true then we will have a lower bound for |X P ℓ (GF (p))| on the order of (2 -1 ℓ )p, along the lines above, by Proposition 1. Proof of claim: It is a well-known fact in algebraic number theory that p ≡ 1 (mod ℓ) implies that the prime p splits completely in the cyclotomic field Q ℓ generated by the ℓ-th roots of unity in C, denoted r1 = 1, r2 , ..., rℓ . The condition χ(r i -1) = 1 means that p splits in the extension of Q ℓ obtained by adjoining √ ri -1 (here i = 2, ..., ℓ). By Chebotarev's density theorem there exist infinitely many such p, as claimed. ✷ In fact, there are effective versions which give explicit information on computing such p [LO], [Se]. This, together with the previous lemma, proves the following result.

Theorem 7 (Voloch) If ℓ ≥ 2 is any fixed integer then for infinitely many primes p there exists a subset S ⊂ GF (p) for which |X S (GF (p))| = (2 -1 ℓ )p + a, where a is a small constant, -1 2 ≤ a ≤ 5 2 . In fact, the primes occurs with a positive (Dirichlet) density and the set S can be effectively constructed.

  1365-8050 c 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

  1 2 elements (⊔ denotes disjoint union). So parity |Q ∩ (a -S)| = parity |Q ∩ (a -S c )| if and only if |Q| is even and parity |Q ∩ (a -S)| = parity |Q ∩ (a -S c )| if and only if |Q| is odd. Conclusion |S| even : T a (S) = x∈a-S x p , |S| odd and p ≡ 3 (mod 4) : T a (S) = -T a (S c ), |S| odd and p ≡ 1 (mod 4) : T a (S) = T a (S c ). The relation between wt(c) and the character sum follows from this. For the remaining part of the equation, use Proposition 1. ✷ Remark 3 It can be shown, using the coding-theoretic results above, that if p ≡ -1 (mod 8) then (for non-empty S) X S (GF (p)) contains at least √ p + 1 points. This also follows from Weil's estimate, but since the proof is short, it is given here. What part c of Proposition 2 gives is that if p ≡ -1 (mod 8) and |S| is odd then X S (GF (p)) contains at least √ p+2 points. If |S| is even then perform the substitution x = a+1/x, y = y/x |S| on the equation y 2 = f S (x). This creates a hyperelliptic curve X in (x, y) for which |X(GF (p))| = |X S (GF (p))| and X ∼ = X S ′ , where |S ′ | = |S| -1 is odd. Now apply part 3 of the above proposition and Remark 1 to X S ′ . ✷ Remark 4 If |S| = 2 or |S| = 3 then more can be said about the character sums above.

Corollary 2

 2 Assume Conjecture 3. If p ≡ 3 (mod 4) then max S |X S (GF (p))| > 5 3 p -4. Example 2 The following examples were computed with the help of SAGE.

  P (T ) is a polynomial of degree n + 2dd ⊥ which only depends on C through its weight enumerator polynomial (here d is the minimum distance of C and d ⊥ is the minimum distance of its dual code C ⊥ ; we assume d ≥ 2 and d ⊥ ≥ 2). If γ = γ(C) = n+k+1-d and z C (T ) = Z C (T )T 1-γ then the functional equation in [D1] can be written in the form z C ⊥ (T ) = z C (1/qT ). If we let ζ C (s) = Z C (q -s ) and ξ C (s) = z C (q -s ) then ζ C and ξ C have the same zeros but ξ C is "more symmetric" since the functional equation expressed in terms of it becomes

  a∈GF (p) χ(f Q (a)) = -p -2 + |X Q (GF (p))|. Since p ≡ 1, 3 (mod 8), we have χ(-2) = 1, so χ(f Q (n)) = 1 for all n ∈ N . It follows that |X Q (GF (p))| = 3 2 p + χ(f Q (0)) + 1 2 (if p ≡ 3 (mod 8)) or |X Q (GF (p))| = 3 2 p + χ(f Q (0)) + 3 2(if p ≡ 1 (mod 8)). ✷

  This is a contradiction.

✷

Corollary 3 Assume Conjecture 3. There is a constant p 0 (ineffectively computable) having the following property: if p > p 0 then there is a subset S ⊂ GF (p) for which the bound |X S (GF (p))| > 1.62p holds.

  ] (self-dual) code C N Q has "zeta polynomial"

	P (T ) =	2 143	+	4 143	T +	19 429	T 2 +	28 429	T 3 +	40 429	T 4 +	56 429	T 5 +	76 429	T 6 +	32 143	T 7 +	32 143	T 8 .
	It can be checked that all the roots ρ of Z C have |ρ| = 1/ this case.	√	2, thus verifying the Riemann hypothesis in

Acknowledgements

I thank Prof. Amin Shokrollahi of the Ecole Polytechnique Fédérale de Lausanne for helpful advice and Prof. Felipe Voloch of the University of Texas for allowing his construction to be included above. Parts of this note (such as Proposition 2) can be found in the honors thesis [C] of my former student Greg Coy, who was a pleasure to work with. Last but not least, I thank the anonymous referees who substantially improved the paper with their insightful suggestions.

In particular, C is linear and of dimension p -1.

Proof: It follows from the the proof of Theorem 4 that if p ≡ 1 (mod 4) then r N r S1 = r N r S2 and

1 . The lemma follows rather easily as a consquence of this and (4). ✷ Assume p ≡ 3 (mod 4). Let

By abuse of terminology, we call C an LQR code. Lemma 7 For each p, the codeword

, p ≡ 1 (mod 4), 2p, p ≡ 3 (mod 4).

In other words, if p ≡ 3 (mod 4) then C is a constant weight code.

Proof: Indeed, Proposition 2 implies if p ≡ 1 (mod 4) then


Yi-Zheng Fan

Jing Xu

Yi Wang

Dong Liang

The Laplacian Spread of a Tree

Keywords: Tree, Laplacian matrix, Spread

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we show that the star is the unique tree with maximal Laplacian spread among all trees of given order, and the path is the unique one with minimal Laplacian spread among all trees of given order.

Introduction

Let G be a simple graph of order n with the vertex set V = V (G) = {v 1 , v 2 , . . . , v n } and the edge set E = E(G). The adjacency matrix of the graph G is defined to be a matrix A = A(G) = [a ij ] of order n, where a ij = 1 if v i is adjacent to v j , and a ij = 0 otherwise. Since A is symmetric and real, the eigenvalues of A can be arranged as follows:

λ n (G) ≤ λ n-1 (G) ≤ • • • ≤ λ 1 (G).
The spread of the graph G is defined as

S A (G) = λ 1 (G) -λ n (G).
Generally, the spread of a square complex matrix M is defined to be s(M ) = max i,j |λ i -λ j |, where the maximum is taken over all pairs of eigenvalues of M . There is a considerable literature on the spread of an arbitrary matrix, see, e.g. [START_REF] Johnson | Lower bounds for the spread of a matrix[END_REF]; [START_REF] Mirsky | The spread of a matrix[END_REF]; [START_REF] Nylen | On the spread of a hermitian matrix and a conjecture of thompson[END_REF]; [START_REF] Thompson | The eigenvalue spreads of a hermitian matrix and its principal submatrices[END_REF]; [START_REF] Zhan | Extremal eigenvalues of real symmetric matrices with entries in an interval[END_REF].

Recently, the spread of a graph has received much attention. In [START_REF] Petrović | On graph whose spectral spread does not exceed 4[END_REF], Petrović determines all minimal graphs whose spreads do not exceed 4. In [START_REF] Gregory | The spread of the spectrum of a graph[END_REF], Gregory, Hershkowitz, and Kirkland present some lower and upper bounds for the spread of a graph. They show that the path is the unique graph with minimal spread among all connected graphs of given order. However the graph(s) with maximal spread is still unknown, and some conjectures are presented in their paper. In [START_REF] Li | The spread of unicyclic graphs with given size of maximum matchings[END_REF], Li, Zhang and Zhou determine the unique graph with maximal spread among all unicyclic graphs with given order not less than 18, which is obtained from a star by adding an edge between some two pendant vertices. In [START_REF] Nikiforov | Linear combinations of graph eigenvalues[END_REF], Nikiforov considers a more general problem: what is the property of the linear combination of some extreme eigenvalues of a graph? He gives a theorem involving the limit of a certain combination as the order of a graph goes to infinity, and presents an upper bound for the sum of the largest eigenvalue and the second largest eigenvalue of all graphs of fixed order.

In this paper, we consider another version of spread of a graph, i.e. the Laplacian spread of a graph, which is defined as follows. Let G be a graph as above. The Laplacian matrix of a graph G is defined as and d(v) denotes the degree of a vertex v of G. It is known that L is symmetric and positive semidefinite so that its eigenvalues can be arranged as follows:

L = L(G) = D(G) -A(G), where D(G) = diag{d(v 1 ), d(v 2 ), . . . , d(v n )} is a diagonal matrix,
0 = µ n (G) ≤ µ n-1 (G) ≤ • • • ≤ µ 1 (G),
where µ n (G) = 0 as each row sum of L is zero. There are a lot of results involving with the relations between the spectrum of L and numerous graph invariants, such as connectivity, diameter, isoperimetric number, and expansion properties of a graph; see, e.g., [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF]; [START_REF] Merris | Laplacian matrices of graphs: a survey[END_REF]; [START_REF] Mohar | Some applications of laplacian eigenvalues of graphs[END_REF]. In particular, µ n-1 (G) > 0 if and only if G is connected. [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF] calls the µ n-1 (G) the algebraic connectivity of the graph G, which is considered as an algebraic measurement of the connectivity of a graph. The corresponding eigenvector of µ n-1 (G) is usually called Fiedler vector, which has a beautiful structural property given by Fiedler (Fiedler, 1975, Theorem 3.14). One can find that µ 1 (G) is exactly the spectral radius of L, which also has a lot of results (especially the upper bounds) for this eigenvalue; see e.g. [START_REF] Das | An improved upper bound for laplacian graph eigenvalues[END_REF]. The Laplacian spread of the graph G is defined to be

S L (G) = µ 1 (G) -µ n-1 (G).
Note that in the definition we consider the largest eigenvalue and the second smallest eigenvalue, as the smallest eigenvalue always equals zero. In addition, throughout this paper we only consider connected graphs G in which case µ n-1 (G) > 0.

We now consider the extremal Laplacian spread of trees. Let P n , S n denote a path and a star of order n respectively. It is known that for any tree T of order n, [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF]; [START_REF] Merris | Characteristic vertices of trees[END_REF]; [START_REF] Chen | Properties of spectra of graphs and line graphs[END_REF].

2 1 + cos( π n ) = µ 1 (P n ) ≤ µ 1 (T ) ≤ µ 1 (S n ) = n, Chen (2002), ( 1
)
2 1 -cos( π n ) = µ n-1 (P n ) ≤ µ n-1 (T ) ≤ µ n-1 (S n ) = 1,
(2) For both inequalities, the left equalities hold if and only if T = P n , and the right equalities hold if and only if T = S n . With equalities (1) and (2), we can not directly tell that S n is the one with maximal

❡ ❡ p pendant vertices ❡ ❡ (n -2 -p) pendant vertices ❡ ❡ ❅ ❅ ❅ ❅ ❅ ❅ Fig. 1: A double star T(n, p) with n -2 ≥ p ≥ (n -2)/2.
Laplacian spread among all trees of order n, and P n is the one with minimal Laplacian spread among all trees of order n.

We focus on the problem of maximizing and minimizing the Laplacian spread of trees, and show that S n and P n are indeed the trees respectively with maximal Laplacian spread and minimal Laplacian spread among all trees of order n. As the problem for a tree with order less than 5 is obvious, throughout the paper we assume all trees has order greater than or equal to 5, unless specified somewhere.

Tree(s) with maximal Laplacian spread

We first narrow down the possibility of the tree(s) with maximal Laplacian spread.

Lemma 1 [START_REF] Anderson | Eigenvalues of the laplacian of a graph[END_REF] Let G be graph. Then

µ 1 (G) ≤ max{d(u) + d(v) : uv ∈ E(G)}.
If G is connected, then the equality holds if and only if G is bipartite and the degree is constant on each partition of the vertices of G.

Denote by ∆(G) the maximum degree of all vertices of a graph G.

Lemma 2 [START_REF] Grone | The laplacian spectrum of a graph II[END_REF] Let G be graph of order n ≥ 2 containing at least one edge. Then

µ 1 (G) ≥ ∆(G) + 1.
If G is connected, then the equality holds if and only if ∆(G) = n -1.

Let T be the one with maximal Laplacian spread among all trees of order n. By Lemma 1, we now prove T is necessarily a double star of order n, i.e., a tree obtained from an edge by attaching p pendant edges to one vertex of the edge and n -2 -p pendant edges to the other vertex of the edge with n -2 ≥ p ≥ (n -2)/2, denoted by T(n, p); see Fig. 1.

Lemma 3 Let T be the one with maximal Laplacian spread among all trees of order n. Then T is a double star T(n, p) for some p with n -2 ≥ p ≥ (n -2)/2.

Proof: Let T be a tree of order n, and let N (v) denote the neighborhood of a vertex v of T . Then for any edge uv of T ,

d(u) + d(v) = |N (u) ∪ N (v)| ≤ n,
with equality if and only if T = T(n, d(u) -1) (assuming d(u) ≥ d(v)). In addition, the star S n = T(n, n -2) and S L (S n ) = n -1.

For any tree T which is not a double star, then by above discussion and Lemma 1,

µ 1 (T ) ≤ max{d(u) + d(v) : uv ∈ E(T )} ≤ n -1. Then S L (T ) = µ 1 (T ) -µ n-1 (T ) < n -1 as µ n-1 (T ) > 0. The result follows. ✷ Proposition 1 The characteristic polynomial of L(T(n, p)) is det(λI -L(T(n, p))) = λ(λ -1) n-4 [(λ -n)(λ -1) 2 + p(n -2 -p)λ]. (3)
Proof: Let q := n -2 -p. By relabelling the vertices if necessary we may write the matrix B := λI -L(T(n, p)) as follows:

B =     (λ -1)I p 0 e p 0 0 (λ -1)I q 0 e q e T p 0 λ -(p + 1) 1 0 e T q 1 λ -(q + 1)     ,
where I p , e p respectively denote an identity matrix of order p and an all-one column vector of dimension p.

Assume that λ = 1. Then by left multiplying a block matrix

I p+q 0 -(λ -1) -1 diag{e T p , e T q } I 2
, the above matrix is transferred into

    (λ -1)I p 0 e p 0 0 (λ -1)I q 0 e q 0 0 -p(λ -1) -1 + λ -(p + 1) 1 0 0 1 -q(λ -1) -1 + λ -(q + 1)     .
Hence

det B = (λ -1) p+q-2 det -p + (λ -1)[λ -(p + 1)] (λ -1) (λ -1) -q + (λ -1)[λ -(q + 1)] = λ(λ -1) n-4 [(λ -n)(λ -1) 2 + p(n -2 -p)λ]
Since the degree of the characteristic polynomial of L(T(n, p)) is finite and there are infinite λ (λ = 1) such that (3) holds, the result holds for all λ ∈ R.

✷ Denote f (λ; n, p) := (λ -n)(λ -1) 2 + p(n -2 -p)λ. ( 4
)
Then the characteristic polynomial of L(S n ) of the star S n is λ(λ -1) n-4 f (λ; n, n -2). For any double star T(n, p) with (n -2)/2 ≤ p ≤ n -3 and n ≥ 5, by (2), (0 <)µ n-1 (T(n, p)) < 1, and by Lemma 2, µ 1 (T(n, p)) ≥ ∆(T(n, p)) + 1 = p + 2 ≥ 4. Hence the eigenvalues µ n-1 (T(n, p)), µ 1 (T(n, p)) are both roots of the polynomial f (λ; n, p). In addition, all roots of f (λ; n, p) must be positive as they are nonzero eigenvalues of L(T(n, p)).

In the following, we shall prove that for (n -2)/2 ≤ p ≤ n -3 and n ≥ 5, S L (T(n, p)) < S L (T(n, n -2)) = n -1. By this inequality and Lemma 3, we then get the result that the star is the unique tree with maximal Laplacian spread among all trees with given order. There are exactly two double stars T(5, 2), T(5, 3) of order 5, and by Lemma 4 above inequality holds for n = 5. There are exactly three double stars of order 6, i.e. T(6, 2), T(6, 3), T(6, 4). By Lemma 4, S L (T(6, 3)) < S L (T(6, 4)). The inequality S L (T(6, 2)) < S L (T(6, 4)) can be obtained directly by a little computation. By (4), f (λ; 6, 2) = (λ -6)(λ -1) 2 + 4λ, which has roots (5 + √ 17)/2, 3, (5 -√ 17)/2. So the Laplacian spread of T(6, 2) is √ 17 < 6 -1 = 5.

Lemma 4 For n ≥ 5,

S L (T(n, n -3)) < S L (T(n, n -2)) = S L (S n ) = n -1.
Proof: By Proposition 1 and the discussion prior to this lemma, the eigenvalues µ n-1 (T(n, n-3)), µ 1 (T(n, n-3)) are both roots of the polynomial

f (λ; n, n -3) = (λ -n)(λ -1) 2 + (n -3)λ = λ 3 -(n + 2)λ 2 + (3n -2)λ -n. Note that f (1/3; n, n -3) = - 23 + 3n 27 < 0, f (n -2/3; n, n -3) = 4 -39n + 9n 2 27 > 0 if n ≥ 5.
If there exists a λ 0 > n -2/3 such that f (λ 0 ; n, n -3) ≤ 0 then f (λ; n, n -3) has two roots both greater than n -2/3, and hence the sum of its root is greater than 2n -4/3. However, the sum of all roots (necessarily be positive) of f (λ; n, n -3) is n + 2 < 2n -4/3, which is a contradiction, for n ≥ 4. So λ 1 (T(n, n -3) < n -2/3. Similarly, we get µ n-1 (T(n, n -3) > 1/3. Hence S L (T(n, n -3)) < (n -2/3) -1/3 = n -1.

The result follows. ✷

Next we consider the Laplacian spread of T(n, p) with (n -2)/2 ≤ p ≤ n -4.

Lemma 5 For (n -2)/2 ≤ p ≤ n -4 and n ≥ 6,

S L (T(n, p)) < S L (T(n, n -2)) = S L (S n ) = n -1.
Proof: For brevity, we simply write µ 1 (T(n, p)), µ n-1 (T(n, p)) as µ 1 , µ n-1 respectively. Observe that

S L (T(n, n -2)) -S L (T(n, p)) = (n -1) -(µ 1 -µ n-1 ) = (n -µ 1 ) -(1 -µ n-1 ).
By (4), if λ > 0, the image of f (λ; n, p) is obtained from f (λ; n, n -2) by adding a positive function p(n -2 -p)λ; see Fig. 2. By Mean-Value Theorem,

n -µ 1 = f (n; n, p) -f (µ 1 ; n, p) f ′ (ξ 1 ; n, p) = np(n -2 -p) f ′ (ξ 1 ; n, p) , 1 -µ n-1 = f (1; n, p) -f (µ n-1 ; n, p) f ′ (ξ 2 ; n, p) = p(n -2 -p) f ′ (ξ 2 ; n, p) ,
for some ξ 1 ∈ (µ 1 , n) and ξ 2 ∈ (µ n-1 , 1), where f ′ (λ; n, p) denotes the derivative of f (λ; n, p) with respect to λ. If we can show np(n -2 -p) f ′ (ξ 1 ; n, p) > p(n -2 -p) f ′ (ξ 2 ; n, p) , or nf ′ (ξ 2 ; n, p) > f ′ (ξ 1 ; n, p), the result will follow. Note that f ′ (λ; n, p) = 3λ 2 -2(n + 2)λ + 2n + 1 + p(n -2 -p).

So f ′ (λ; n, p) is strictly decreasing on the open interval (0, (n + 2)/3) and is strictly increasing on ((n + 2)/3), +∞). Note that 0 < ξ 2 < 1 < (n + 2)/3, and by Lemma 2, n > ξ 1 > µ 1 ≥ p + 2 ≥ (n -2)/2 + 2 > (n + 2)/3. Therefore, nf ′ (ξ 2 ; n, p) > nf ′ (1; n, p) = np(n -2 -p), f ′ (ξ 1 ; n, p) < f ′ (n; n, p) = (n -1) 2 + p(n -2 -p).

Then nf ′ (ξ 2 ; n, p) -f ′ (ξ 1 ; n, p) > (n -1)[p(n -2 -p) -(n -1)].

As (n -2)/2 ≤ p ≤ n -4, p(n -2 -p) -(n -1) ≥ 2(n -4) -(n -1) = n -7. So, if n ≥ 7, the result follows. If n = 6, then p = 2 and this case is verified prior to Lemma 4. ✷ By Lemmas 3, 4 and 5, we get the main result.

Fig. 2 :

 2 Fig. 2: The images of f (λ; n, p) with (n -2)/2 ≤ p ≤ n -3 and f (λ; n, n -2).

Acknowledgements

The authors would like to thank the anonymous referees for valuable suggestions and corrections, which have improved the original manuscript.

† Supported by National Natural Science Foundation of China (10601001), Anhui Provincial Natural Science Foundation (050460102, 070412065), Foundation of Innovation Team on Basic Mathematics of Anhui University.

‡ Supported by National Natural Science Foundation of China (60772121), NSF of Department of Education of Anhui Province (2005KJ005ZD), Foundation of Innovation Team on Eletrocircuit Design and Measure Technology of Anhui University.

§ Current corresponding address.

1365-8050

Theorem 1 For n ≥ 5, the star is the unique tree with maximal Laplacian spread among all trees of order n.

Tree(s) with minimal Laplacian spread

We first establish a relation between the Laplacian spread of a tree and the (adjacency) spread of the line graph of the tree, and then use the relation to obtain another main result of this paper.

Let T be a tree of order n with vertices v 1 , . . . , v n and edges e 1 , . . . , e n-1 . The (vertex-edge, unoriented) incidence matrix of T is the n × (n -1) matrix M (T ) = [m ij ] given by: m ij equals 1 if vertex v i is incident to edge e j and equals 0 otherwise. The unoriented Laplacian matrix K(T ) of T is defined to be the n

The line graph of the tree T , denoted by T l , is the graph whose vertices are exactly the edges of T with two vertices being adjacent if and only if the the corresponding edges in T are incident. One can find that M (T ) T M (T ) = 2I n-1 + A(T l ) (or see (Brualdi and Ryser, 1991, p. 35)). Note that T l is connected, and P l n = P n-1 for n ≥ 3. Lemma 6 [START_REF] Grone | The laplacian spectrum of a graph[END_REF] Let G be a bipartite graph. Then K(G) = D(G) + A(G) and L(G) = D(G)-A(G) are unitarily similar, i.e., there exists an orthogonal matrix U such that K(G) = U -1 L(G)U .

Lemma 7 For any tree T of order n ≥ 3, the Laplacian spread of T is exactly the (adjacency) spread of T l , i.e., S L (T ) = S A (T l ).

Proof: As T is bipartite, by Lemma 6, the matrix Theorem 2 For n ≥ 5, the path is the unique tree with minimal Laplacian spread among all trees of order n.

Proof: Let T be any tree of order n ≥ 5, which is not a path. Then T l is a connected graph of order n -1 which is not a path. Then by Lemmas 7 and 8, S L (T ) = S A (T l ) > S A (P n-1 ) = S A (P l n ) = S L (P n ).

The result follows. ✷


Dorota Bród
email: dorotab@prz.edu.pl

Zdzisław Skupień
email: skupien@agh.edu.pl

Recurrence among trees with most numerous efficient dominating sets

Keywords: Mathematics Subject Classification: 05C69, 05C05, 05C35, 05C75, 05A15 counting, efficient domination, structural characterization, trees

A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization of all maximum trees is given. Their structure has recurring aspects with period 7. Moreover, the number of efficient dominating sets in maximum nvertex trees is determined and is exponential. Also the number of maximum n-vertex trees is shown to be bounded below by an increasing exponential function in n.

Introduction

Our aim is to maximize the number of efficient dominating sets among n-vertex trees. This is a sequel to our article [START_REF] Bród | Trees with extremal numbers of dominating sets[END_REF]. Paper [START_REF] Bród | Trees with extremal numbers of dominating sets[END_REF] presents characterizations of trees with largest or smallest (and still large) numbers of dominating sets. Trees without any efficient dominating set exist. Determining whether or not a graph has an efficient dominating set is an NP-complete problem, see [START_REF] Bange | Efficient dominating sets in graphs[END_REF][START_REF] Hedetniemi | Complexity Results[END_REF]. A constructive characterization of trees which have an efficient dominating set can be found in [START_REF] Bange | Efficient dominating sets in graphs[END_REF]. That is why we concentrate on characterizing trees with the largest number of efficient dominating sets. There are several papers devoted to characterizing graphs with maximal numbers of specified substructures. Erdős is credited for raising a question which is answered in the pioneering paper [START_REF] Moon | On cliques in graphs[END_REF] of 1965 by Moon and Moser on maximizing the number of cliques among n-vertex graphs. There is a series of publications on the related problem of maximizing the number of maximal independent sets among different graphs, and trees also are considered [START_REF] Wilf | The number of maximal independent sets in a tree[END_REF][START_REF] Sagan | A note on independent sets in trees[END_REF][START_REF] Zito | The structure and maximum number of maximum independent sets in trees[END_REF]. At the beginning of 1980s Tomescu, when dealing with cliques in specialized hypergraphs, studied [START_REF] Tomescu | Le nombre maximum de cliques et de recouvrements par cliques des hypergraphes chromatiques complets[END_REF] number-theoretical problem of maximizing a constrained product of binomial coefficients, the simplest possible subcase of the problem being solved by Moon and Moser [START_REF] Moon | On cliques in graphs[END_REF]. The second author, when dealing with maximizing the number of maximum path-factors among trees, arrived independently [START_REF] Skupień | On counting maximum path-factors of a tree[END_REF] at another subcase of Tomescu's problem. A solution to Tomescu's problem was found by Schinzel and Skupień, cf. [START_REF] Skupień | From tree path-factors and doubly exponential sequences to a binomial inequality[END_REF].

Given a graph G, a vertex set S ⊆ V (G) is called a dominating set of G if any vertex of G either is in S or has a neighbor in S. Following Bange et al. [START_REF] Bange | Disjoint dominating sets in trees[END_REF], a dominating set D of G is called an EDS (efficient dominating set) if the distance between any two members of D is at least three in G. Bange, Barkauskas and Slater [START_REF] Bange | Efficient dominating sets in graphs[END_REF] proved the following result.

Proposition 1 If G has an efficient dominating set, then the cardinality of any efficient dominating set equals the domination number of G. In particular, all efficient dominating sets have the same cardinality.

The number of efficient dominating sets in oriented graphs, and in particular, oriented trees was studied [START_REF] Barkauskas | Finding efficient dominating sets in oriented graphs[END_REF][START_REF] Schwenk | Efficient dominating sets in labeled rooted oriented trees[END_REF].

Observation 1 Given any dominating set D of a graph G, if v ∈ V (G) then either v ∈ D or a neighbor of v is in D. If D is any EDS and v / ∈ D then exactly one neighbor of v is in D. ✷
Let T n be the class of unlabeled trees of order n, where isomorphic trees are considered identical. In what follows T stands for a tree with vertex set V (T ), |T | denotes the cardinality of V (T ). A leaf (or pendant vertex) and a B-vertex (or branch vertex) are vertices of degree at most one and at least three, respectively. Let B(T ) and b(T ) denote respectively the set and number of B-vertices in T . A twig in T is a nontrivial path joining a leaf of T to the closest vertex in T which is not of degree two. Hence the number of twigs, say θ(T ), either is the number of leaves if b(T ) > 0 or is one less than the number of leaves if T is a path (whether trivial or not). Given an i ∈ {0, 1, 2} and x ∈ B(T ), let τ i (x) be the number of twigs attached to x with lengths congruent to i modulo 3.

Let T have a B-vertex. Consider the subtree obtained by ungluing all twigs from T (i.e., by deleting all non-B-vertices of twigs together with all incident edges). Then every pendant vertex x of the subtree is called a P B-vertex (or a pendant B-vertex) of T . Let P B(T ) stand for the set of pendant branch vertices in T .

Let q(T ) denote the number of all efficient dominating sets of T . Given a positive integer n, let q(n) denote the maximum of q(T ) over all trees T on n vertices, n = |T |. Then each n-vertex tree such that q(T ) = q(n) is called a maximum tree.

We shall characterize all maximum trees T on n vertices. If n ≥ 9 then the structure of T is quite easy to describe. Namely, each maximum tree T has uniquely defined number b of branch vertices, b = b(n). Branch vertices induce a subtree, and all remaining vertices of T are on twigs of length two only. with s = -1, 0, 1, . . . , 5 provided that b ≥ 5. Thus s, which determines some structural aspects, is a periodic function of n with period 7. Our main result is that any tree on b vertices is a subtree induced by branch vertices of an n-vertex maximum tree with n such that b = b(n). Additionally we give a detailed specification of the following estimation. The number of maximum trees on n vertices is exponential in n because, for n ≥ 39, it is at least the number |T b | of all trees on b vertices with b = b(n) ∼ n/7 as n → ∞, the lower bound being attained if 7|n and n ≥ 35. We determine q(n), and q(n) is exponential in n, too.

EDS' and maximum trees can possibly be used to design computer or communication networks, facility and guard locations, surveillance systems, interference-free transmission and/or cooperation, cf. [7, p. 891].

Preliminaries

Using Proposition 1 we can see that in case of a nontrivial path P n (n ≥ 2) each efficient dominating set of P n contains no endvertex, both endvertices and exactly one endvertex depending on whether n is congruent modulo 3 to 0, 1, 2, respectively. Hence the number of efficient dominating sets in P n is

q(P n ) = 1 if n ≡ 0, 1 (mod 3), 2 if n ≡ 2 (mod 3). ( 1
)
Assume that T is a tree with a twig P of length 3 or more. Let z be a leaf of T in P and wxyz a subpath in P . Then wxyz is called a terminal subtwig in T . The transformation T → T -{x, y, z} is called a 3-reduction of T . Recursive repetition of a 3-reduction eventually gives a subtree of T , say T , which does not have any twig of length 3 or more. Call T to be the 3-trim of T .

Proposition 2 Any 3-reduction T → T ′ does not change the number of EDS', i.e., q(T ′ ) = q(T ).

Proof: Given a leaf z of T such that wxyz is a terminal subtwig in T , let T ′ = T -{x, y, z}. Due to Observation 1 and the definition of EDS, if D is an EDS of T then {z, w} ⊆ D or, if

T = P 4 , {y, u} ⊆ D where u is a neighbor of w in T ′ . Hence, for each D, D -{z, y} is an EDS of T ′ . Conversely, if D ′ is any EDS of T ′ then, due to Observation 1 (with v = w in T ′ ), D ′ is uniquely augmentable to an EDS of T . Therefore D → D -{z, y} is a bijection from EDS' in T onto those in T ′ . ✷ Corollary 1 q( T ) = q(T ) if T is the 3-trim of T . ✷
Recall that for x ∈ B(T ), τ i (x) is the number of twigs of length congruent to i modulo 3, i = 0, 1, 2, twigs being attached to x.

Proposition 3 Let T be a tree with exactly one branch vertex x. Let τ i = τ i (x). Then

q(T ) =            0 if τ 2 ≥ 1 and τ 1 ≥ 2, 1 if τ 2 ≥ 1 and τ 1 = 1 or τ 2 = 0 and τ 1 ≥ 2, or τ 2 = τ 1 = 0, 2 if τ 2 = 0 and τ 1 = 1, τ 2 if τ 2 ≥ 1 and τ 1 = 0. ✷ Corollary 2
Let T be an n-vertex tree with b(T ) = 1, n ≥ 7, n = 8, and with q(T ) being the largest possible number of EDS'. Then τ 1 = 0 and q(T ) = τ 2 ≥ 3 where

τ 2 = n-1 2 for odd n, n-4 2
for even n, whence all twigs are of length 2 but one of length 3 for even n only. ✷

Useful recursive relations

We are going to present a recurrence relations for the number q(T ). Assume that b(T ) ≥ 2 and x is a P B-vertex. Then there exists a unique vertex a(x) which is the neighbor of x on a path from x to another B-vertex in T . The vertex a(x) is said to be the attachment vertex of x. Let T - * x be the tree obtained from T by deleting the P B-vertex x together with all twigs attached to x. Call T - * x to be tree T minus star at x. Let T a(x)+i stand for a tree obtained from T - * x by adding a new y-a(x) path of length i = 0, 1, 2, where y = a(x) if i = 0. Let q(T a(x)+i , y) be the count of all efficient dominating sets that contain y. The following result is easily seen due to Observation 1.

Lemma 1 Let b(T ) ≥ 2 and τ 0 = 0 at all B-vertices of T . Assume that x ∈ P B(T ), a(x) is the attachment vertex of x, and τ i = τ i (x) for i = 1, 2. Let y be the endvertex of path y-a(x) of length j = 0, 1, 2 in the tree T a(x)+j . Then

q(T ) =        0 if τ 1 ≥ 2 and τ 2 ≥ 1, q(T a(x)+1 , y) if τ 1 ≥ 2 and τ 2 = 0, q(T a(x)+2 , y) if τ 1 = 1 and τ 2 ≥ 1, τ 2 (x)q(T a(x)+2 , y) + q(T a(x)+0 , y) if τ 1 = 0 and τ 2 ≥ 2.

✷

One can easily check that orders of trees T a(x)+1 and T a(x)+2 involved in Lemma 1 are at most |T | -2. Using some of the above results and inspecting the list of small trees in Harary [START_REF] Harary | Graph Theory[END_REF] gives the following. Proposition 4 All trees T on n vertices with n ≤ 10 which are maximum, i.e., with q(T ) = q(|T |), are listed in Fig. 1, T being unique if n = 4, 6, 8.

✷ The symbol S(G) (which appears in Fig. 1) stands for subdivision graph of G. Recall that S(G) results in inserting a new vertex of degree 2 into each edge of G.

A vertex x of a tree T is called EDS-avoided if x does not belong to any efficient dominating set of T .

Proposition 5 Each tree of order n ≥ 3 has an EDS-avoided vertex. In fact, each vertex at distance 2 from a leaf is EDS-avoided. ✷ Lemma 2 Let b(T ) ≥ 2, x ∈ P B(T ), τ 1 (x) = τ 0 (x) = 0, and τ 2 (x) ≥ 2. Then

q(T ) ≤ τ 2 (x) q(T - * x),
where T minus star at x is involved, and equality is true if and only if a(x), the attachment vertex of x, is EDS-avoided in T - * x (i.e., q(T a(x)+0 , y) = 0).

Proof: On applying Lemma 1 we have

q(T ) = q(T a(x)+0 , y) + τ 2 (x) q(T a(x)+2 , y). (2)
Due to Observation 1, one can see that q(T - * x) = q(T a(x)+0 , y) + q(T a(x)+2 , y). Hence, by [START_REF] Bange | Efficient dominating sets in graphs[END_REF],

q(T ) = q(T a(x)+0 , y) + τ 2 (x) [q(T - * x) -q(T a(x)+0 , y)] = τ 2 (x) q(T - * x) + [1 -τ 2 (x)] q(T a(x)+0 , y) ≤ τ 2 (x) q(T - * x),
where equality holds whenever q(T a(x)+0 , y) = 0, which ends the proof. ✷ r r r r r r r r r r n = 10, q = 4, H:

r r r r ✑ ✑ ✑ ✑ ◗ ◗ ◗ ◗ r r r r r n = 9, q = 4, S(K 1,4 ): r r r r r ✑ ✑ ✑ ✑ r r r n = 8, q = 2, T = P 8 , or r r r r r ✑ ✑ ✑ ✑ ✑ r r r r r r r r n = 7, q = 3, S(K 1,3 ): r r ✑ ✑ ✑ ✑ r r r r r r n = 6, q = 1, T = P 6 , K 1,5 , or r r r r ✁ ✁ ✁ r r
For n = 1, 2, 3, 5, T = P n (uniquely), q ∈ {1, 2}, n = 4, q = 1, T = P 4 or K 1,3 (5)

q(T ) = θ(T ) if b(T ) = 1, (6) 7 ≤ |T | = 8, (7)
θ(T ) = x∈B(T ) τ 2 (x) ≥ max{2b(T ), 3} ≥ 3. (8)

✷

The following observation complements Proposition 5.

Proposition 7 If T ∈ T 2 then EDS-avoided vertices in T coincide with B-vertices. ✷ From ( 6), Lemma 2 and Proposition 7, for T ∈ T 2 , we get the following.

q(T ) = x∈B(T ) τ 2 (x). ( 9
)
Observation 2 The RHS (right-hand side) of ( 9) determines the corresponding tree T up to the distribution of twigs in the following sense.

Consider a finite product i∈I t i of integers t i ≥ 2 where |I| ≥ 1. Let b = |I|, the number of factors in the product, θ = i∈I t i , the sum of factors, and let n = b + 2θ. Let T b be any tree on b vertices with arbitrarily assigned mutually distinct labels x i , i ∈ I. Let T be a tree obtained from T b by attaching t i twigs of length two to the vertex x i for each i ∈ I. Hence τ 2 (x i ) = t i , T ∈ T 2 n , and q(T ) = i∈I t i . For n ≥ n b , let T due to (8), [START_REF] Moon | On cliques in graphs[END_REF], and Lemma 3.

✷ Let q 2 (n) denote the maximum of q(T ) among n-vertex trees T ∈ T 2 where n = |T | satisfies require- ment (7). Let T 2,max = {T ∈ T 2 : q(T ) = q 2 (|T |)}, each element of T 2,max is called a T 2 -maximum tree. Let T 2,max n stand for the subset of T 2,max comprising n-vertex elements. Let b 2 (n) be the largest b(T ) among T 2 -maximum n-vertex trees T , T ∈ T 2,max n . Small trees T ∈ T 2 n
have the unique b(T ), either 1 or 2 (as determined by the parity of n), and then q 2 (n) can be obtained from [START_REF] Moon | On cliques in graphs[END_REF]. Namely (see Tab. 1),

b 2 (n) = 1 and q 2 (n) = n -1 2 for odd n, n 1 = 7 ≤ n < n 3 = 15, b 2 (n) = 2 and q 2 (n) = n -2 4 • n -2 4
for even n, n 2 = 10 ≤ n < n 4 = 20.

Then T ∈ T

(n) 1 1 2 1 2 1 2 2 2 q 2 (n) 3 4 2 • 2 5 2 • 3 6 3 • 3 3 • 4 4 • 4
For larger n, if n is fixed and T ranges over T 2 n then, by ( 3) and ( 5), b = b(T ) ranges over all natural numbers ≤ n/5 such that b ≡ n (mod 2). Then q 2 (n) can be found by inspection using Corollary 3. Namely, for each admissible value of b, we find θ and next q(T ). Then q 2 (n) is the largest of numbers q(T ) thus found. Moreover, the corresponding b equals b 2 (n).

Let RHS stand for the product on the right-hand side of formula [START_REF] Sagan | A note on independent sets in trees[END_REF]. Then b(T ) is the sum of two exponents of which one can be 0, θ is the sum of the single factors in RHS, cf. [START_REF] Hedetniemi | Complexity Results[END_REF]. Consequently, formula (4) gives n.

The results of search for two largest products, L < R, where both L and R are RHS corresponding to a fixed n, are presented in Tab. 2 for some values of n as stated. Consequently, for those n, R = q 2 (n) whence the corresponding b = b 2 (n). if n mod 7 = 1, 3,

q 2 (n) = 2 • 3 b-1 if n mod 7 = 5, 3 b-s • 4 s otherwise =      2 • 3 n-5 (14)
if n mod 7 = 5, 3 (n-9(7+(n mod 7))/2)/7 • 4 (7+(n mod 7))/2 if n mod 7 = 1, 3, 3 (n-9(n mod 7)/2)/7 • 4 (n mod 7)/2 otherwise.

(

) 15
Tab. 4:

s -1 0 1 2 3 4 5 n mod 7 5 0 2 4 6 1 3

Proof: By Proposition 8, m 3 = b-m 2 -m 4 . Hence, by ( 4) and ( 8), n = b+2θ = b+4m 2 +6m 3 +8m 4 = 7b + 2(m 4 -m 2 ) = 7b + 2s whence [START_REF] Skupień | From tree path-factors and doubly exponential sequences to a binomial inequality[END_REF]. Consequently 7|n -2s. Hence, by Proposition 8, we get Tab. 4 whence ( 12) and ( 14) follow. On the other hand,

q 2 (n) = 2 m2 3 m3 4 m4 ,
where m 2 m 4 = 0, which implies [START_REF] West | Introduction to Graph Theory[END_REF]. ✷

  To define b = b(n) for any n ≥ 39 or odd n ≥ 33, let b = ⌊ n+2 7 ⌋. Then b is an integer such that b ≡ n (mod 2) and b ∈ { b, b -1}. Note that if 7|n and n ≥ 35 then b = n/7. Moreover, b(n) = b for all n = 7b + 2s

Fig. 1 : 3 ) 6

 136 Fig. 1: All maximum n-vertex trees T with n ≤ 10

2 n

 2 (b) comprise T ∈ T 2 n with b(T ) = b and such that q(T ) is the largest possible. Lemma 3 If T ∈ T 2 n (b) and b > 1 then the numbers τ 2 at any two B-vertices of T differ by at most one. Proof: If values of τ 2 are m and k such that m > k + 1 then mk < (m -1)(k + 1) whence making the values closer one to another (by moving a twig from one B-vertex to the other) increases the value of q. ✷ Corollary 3 If T ∈ T 2 n (b) and θ = θ(T ) then θ = (n -b)/2 by (4) and (5), q(T ) = ⌊θ/b⌋ b-(θ mod b) ⌈θ/b⌉ θ mod b (10)

Theorem 1 11 ) 8 Theorem 2 1 2

 111821 Maximum product R = q 2 (n) and the corresponding b = b 2 (n) for each admissible n ≤ 40 are presented in Tab. 3. For each n such that n = 7 or 9 ≤ n ≤ 40, Tab. 3 presents both the number q 2 (n) of efficient dominating sets and the number b = b 2 (n) of B-vertices in any T ∈ T 2,max n For a T ∈ T 2,max n , m k := |{x ∈ B(T ) : τ 2 (x) = k}|. (Proposition Let T ∈ T 2,max n where n ≥ 39 or n = 33, 35, 37. Then m k = 0 unless k ∈ {2, 3, 4}. Hence b(T ) = m 2 + m 3 + m 4 . Additionally, m 2 m 4 = 0, m 2 ≤ 1, m 4 ≤ 5, and m 3 is unbounded. The stated bounds on n (odd n ≥ 33 or any n ≥ 39) are sharp because m 2 = 2 if n = 31 or 38. Proof: Tab. 1 and products L together with the corresponding values of n in Tab. 2 are chosen so as to show that, for a T ∈ T 2,max n , all the factors τ 2 = k = 3 have bounded multiplicity m k . Namely, m k = 0 for k = 7, 8, 9 by Tab. 2 and for k = 7+r ≥ 10 because then 7+r < 3 2 r with n = 15+2r and b ∈ {1, 3}. Furthermore, products L at n = 24, 26 show that m 6 = 0 if n is not too small. Actually m 6 = 0 for n ≥ 14 and the bound is tight because q 2 (13) = 6 (Tab. 1). Similarly, products L at n = 38, 47 and R at n = 29 show that m 5 = 0 for n ≥ 30. Analogously, products L at n = 45, 52 show that m 2 ≤ 1 for large n. On the other hand, products R at n = 47, 54 show that m 2 = 1 is possible for large n. Products R at n = 45, 52 show that m 4 ≥ 5 is allowed for large n but, due to L at n = 54, m 4 = 5 at most. Lemma 3 implies that m 2 m 4 = 0. The value m 2 = 2 in R for n = 31 and 38 shows sharpness of the stated bounds for n. ✷ A tree T is called a large tree if its order |T | ≥ 39 or |T | = 33, 35, 37. Let T be a large tree from T 2,max n , b = b(T ), and s = m 4 -m 2 whence s = -1, 0, . . . , 5, s = -1 if m 2 = 1, otherwise s = m 4 . Then s uniquely depends on n (Tab. 4), • even (n mod 7, 7 + (n mod 7)) otherwise,

Acknowledgements

The authors thank the referees for careful reading and stimulation which resulted in improving and simplifying the presentation of results.

Tab. 2: Inequalities L < R = q2(n) for some n ≥ 15 Tab. 2 serves two purposes. Firstly, it suggests that the function b 2 weakly increases when restricted to n of either parity. Moreover, each value of b displayed within parentheses in Tab. 2 is first attained at the corresponding underlined value of n so that b = b 2 (n) for that n and all larger n which are smaller than the next underlined one. Secondly, if L is displayed at n = k then no q 2 (n) with n ≥ k includes L as a subproduct. Otherwise replacing L in q 2 (n) by the corresponding R = q 2 (k) gives q(T ) as in formula [START_REF] Moon | On cliques in graphs[END_REF] where |T | = n, T ∈ T 2 n , and q(T ) > q 2 (n), a contradiction.

Dorota Bród and Zdzisław Skupień

Theorem 3 For n ≥ 38, q 2 (n + 1) > q 2 (n).

Proof: The inequality holds for n = 38, see Tab. 3. Otherwise, using formula [START_REF] West | Introduction to Graph Theory[END_REF] we get the following quotients all larger than 1. In order to see this result, consider the case n mod 7 = r, r = 0, . . . , 6. Next on finding (n+1) mod 7, use formula [START_REF] West | Introduction to Graph Theory[END_REF]. ✷

The function q 2 is not monotone because of its small values precisely at n = 15, 22, 29. Moreover, q 2 (n + 1) = q 2 (n) precisely for n = 23, 30, 37. Nevertheless, the following important result holds.

Lemma 4 For n ≥ 7 and n = 8, q 2 (n + 3) > q 2 (n).

Proof: The result follows from Tab. 3 for n ≤ 37; otherwise from Theorem 3. ✷

Main results

For maximum trees T with |T | ≤ 10, see Proposition 4. Proof: Theorem is true for n = 7, 9, 10 by Proposition 4. Let T be a maximum tree of order n ≥ 11.

Then q(T ) ≥ q 2 (n) ≥ 5 by Tab. 3 and Lemma 4. Due to Corollary 2, for even n ≥ 10 each n-vertex tree T with b(T ) = 1 has q(T ) ≤ n-4 2 < q 2 (n) by Tab. 3 and Theorem 2. Therefore b(T ) = 1 is possible only if n is odd and then by Corollary 2 maximum tree is T 2 -maximum.

We proceed by induction on n. Consider the case b(T ) ≥ 2. For any fixed x ∈ B(T ), let

A. All twigs in T have length 1 or 2 (whence τ 0 = 0). Due to Lemma 1, there is no x ∈ P B(T ) with τ 1 ≥ 2 and τ 2 ≥ 1. Hence precisely two following subcases A1, A2 are possible.

A1. There exists an x ∈ P B(T ) such that (i) τ 1 ≥ 2 and τ 2 = 0 or (ii) τ 1 = 1 and τ 2 ≥ 1. Let

, we use Lemma 1, and we see that q(T ) ≤ q(T ′ ). Let T ′′ be a maximum tree of order |T ′ |. Then T ′′ ∈ T 2 . Attaching a twig of length 2 to a P B-vertex of T ′′ gives a tree T ⋆ of order |T | such that T ⋆ ∈ T 2 and, by [START_REF] Moon | On cliques in graphs[END_REF], q(T ⋆ ) > q(T ′′ ) ≥ q(T ′ ) ≥ q(T ), a contradiction. A2. τ 1 = 0 and τ 2 ≥ 2 for each x ∈ P B(T ). Let n = 11. Consider an auxiliary 6-vertex graph H of the capital letter H. Then T = S(H), the subdivision of H, is the only possibility. However, q(T ) = 1 < q 2 (11) = 5, a contradiction, cf. Tab. Moreover, by Lemma 2, q(T ) ≤ τ 2 • q(T ′ ) where the equality holds whenever the attachment vertex a(x) is EDS-avoided in T ′ and T ′ is a maximum tree since so is T . Therefore if |T ′ | = 8 then, by induction hypothesis, T ′ ∈ T 2 whence, by Proposition 7, T ∈ T 2 (as required). Otherwise |T ′ | = 8, each maximum T ′ has an EDS-avoided vertex and q(T ′ ) = 2, cf. Proposition 4. Consequently, q(T ) = 2τ 2 (x). Hence, by Observation 2, q(T ) = q(T ′′ ) for some

B. T has a twig of length 3 or more. Assume that a tree T ′ is a 3-reduction of T whence

By Proposition 2, q(T ′ ) = q(T ). Moreover, T ′ is clearly a maximum tree on |T | -3 vertices.

If |T ′ | = 8 then q(T ′ ) = 2 by Proposition 4. However, |T | = 11 and q(T ) ≥ 5 by Tab. 3 whence q(T ) = q(T ′ ), a contradiction. Otherwise |T ′ | ≥ 9 and T ′ ∈ T 2 by the induction hypothesis. Due to Lemma 4, q 2 (|T ′ | + 3) > q(T ′ ), a contradiction to q(T ) = q(T ′ ). Proof: Let n be a natural number, n ≥ 39 or n = 33, 35, 37. Then n = 7b + 2s with s = -1, 0, . . . , 5 and b ≥ 5 being uniquely defined in ( 12) and ( 13), respectively. Due to Theorem 4, any maximum nvertex tree, T , is an element of T 2,max n . The structural parameters m k of T , defined in formula [START_REF] Schwenk | Efficient dominating sets in labeled rooted oriented trees[END_REF], are determined in Proposition 8 and Theorem 2 in terms of s. Hence, due to very definition of the class T 2 in Sect. 4 and Observation 2, the tree T is obtained in the following way. Choose any tree T ′ on b vertices, select a subset S of |s| vertices in T ′ ; for s = 0, attach two or four twigs of length two to each vertex in S according as s = -1 or s > 0, and, finally, attach three such twigs to each of remaining vertices in T ′ . Then the resulting graph includes T ′ as an induced subgraph and has really 7b + 2s vertices as required. Define r t (T ′ ) to be the number of distinct selections of t vertices in T ′ , t ≤ b, two such selections being distinct if no automorphism of T ′ transforms one selection into another. Therefore Notice in this context the importance of Observation 2. It shows how to pass from an integer q to a variety of trees T such that q(T ) = q (but to a single T only, if q is a prime).

✷

We conclude this paper with a few open problems that we find interesting. Let d G (x, y) stand for the distance between vertices x and y in G. Let p be a positive integer, p ≥ 1. A vertex subset S * , S * ⊆ V (G), is called an efficient p-dominating set of G if the following two properties are satisfied.

• for each x / ∈ S * , there exists y ∈ S * at distance at most p from x, d G (x, y) ≤ p,

• the distance between any two vertices of S * is at least 2p + 1 (i.e. d G (x, y) ≥ 2p + 1), if x, y ∈ S * and x = y.

Thus an efficient dominating set is efficient 1-dominating.

Open problems. For any integer p ≥ 2, characterize trees

(1) which have an efficient p-dominating set,

(2) which have a fixed order and the largest number of efficient p-dominating sets.


David R Wood
email: david.wood@upc.es

Bounded-Degree Graphs have Arbitrarily Large Queue-Number

Keywords: graph, queue layout, queue-number, track layout, track-number Mathematics Subject Classification: 05C62 (graph representations), 05C30 (enumeration of graphs and maps)

It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all ∆ ≥ 3 and for all sufficiently large n, there is a simple ∆-regular n-vertex graph with queue-number at least c √ ∆n 1/2-1/∆ for some absolute constant c.

Introduction

We consider graphs possibly with loops but with no parallel edges. A graph without loops is simple. Let G be a graph with vertex set V (G) and edge set E(G). If S ⊆ E(G) then G[S] denotes the spanning subgraph of G with edge set S. We say G is ordered if V (G) = {1, 2, . . . , |V (G)|}. Let G be an ordered graph. Let ℓ(e) and r(e) denote the endpoints of each edge e ∈ E(G) such that ℓ(e) ≤ r(e). Two edges e and f are nested and f is nested inside e if ℓ(e) < ℓ(f ) and r(f ) < r(e). An ordered graph is a queue if no two edges are nested. Observe that the left and right endpoints of the edges in a queue are in first-in-first-out order-hence the name 'queue'. An ordered graph G is a k-queue if there is a partition

{E 1 , E 2 , . . . , E k } of E(G) such that each G[E i ] is a queue. Let G be an (unordered) graph. A k-queue layout of G is a k-queue that is isomorphic to G.
The queue-number of G is the minimum integer k such that G has a k-queue layout. Queue layouts and queuenumber were introduced by Heath et al. [START_REF] Heath | Comparing queues and stacks as mechanisms for laying out graphs[END_REF][START_REF] Heath | Laying out graphs using queues[END_REF] in 1992, and have applications in sorting permutations [START_REF] Even | Queues, stacks, and graphs[END_REF][START_REF] Nozaki | Generating and sorting permutations using restricteddeques[END_REF][START_REF] Ordman | Permutations using stacks and queues[END_REF][START_REF] Vaughan | Computing permutations with double-ended queues. Parallel stacks and parallel queues[END_REF][START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF], parallel process scheduling [START_REF] Sandeep | Scheduling tree-dags using FIFO queues: A control-memory trade-off[END_REF], matrix computations [START_REF] Pemmaraju | Exploring the Powers of Stacks and Queues via Graph Layouts[END_REF], and graph drawing [START_REF] Di | Computing straight-line 3D grid drawings of graphs in linear volume[END_REF][START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF]. Other aspects of queue layouts have been studied in [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF][START_REF] Vida | On linear layouts of graphs[END_REF][START_REF] Vida | Stacks, queues and tracks: Layouts of graph subdivisions[END_REF][START_REF] Ganley | Stack and queue layouts of Halin graphs[END_REF][START_REF] Madhavan | Stack and queue number of 2-trees[END_REF][START_REF] Shi | On crossing sets, disjoint sets, and pagenumber[END_REF][START_REF] Wood | Queue layouts of graph products and powers[END_REF].

Prior to this work it was unknown whether graphs of bounded degree have bounded queue-number. The main contribution of this note is to prove that there exist graphs of bounded degree with arbitrarily large queue-number.

Theorem 1 For all ∆ ≥ 3 and for all sufficiently large n > n(∆), there is a simple ∆-regular n-vertex graph with queue-number at least c √ ∆n 1/2-1/∆ for some absolute constant c.

The best known upper bound on the queue-number of a graph with maximum degree ∆ is e(∆n/2) 1/2 due to Dujmović and Wood [START_REF] Vida | On linear layouts of graphs[END_REF] (where e is the base of the natural logarithm). Observe that for large ∆, the lower bound in Theorem 1 tends toward this upper bound. Although for specific values of ∆ a gap remains. For example, for ∆ = 3 we have an existential lower bound of Ω(n 1/6 ) and a universal upper bound of O(n 1/2 ).

Closely related to a queue layout is the notion of a track layout. Informally speaking, a track layout of a graph consists of a proper vertex colouring, and a total order of each colour class, such that between each pair of colour classes, no two edges cross (with respect to the orders of the colour classes that contain the endpoints of the edges). The track-number of a graph G, denoted by tn(G), is the minimum number of colours in a track layout of G; see [4-7, 9-11, 13]. Dujmović et al. [START_REF] Vida Dujmovi | Layout of graphs with bounded tree-width[END_REF] proved that qn(G) ≤ tn(G) -1. Thus a lower bound on the queue-number also provides a lower bound on the track-number (i) . In particular, Theorem 1 implies:

Theorem 2 For all ∆ ≥ 3 and for all sufficiently large n > n(∆), there is a simple ∆-regular n-vertex graph with track-number at least c √ ∆n 1/2-1/∆ for some absolute constant c.

Note that there is also a O(n 1/2 ) upper bound on the track-number of graphs with bounded degree. The best result is tn(G) ≤ 5∆(G) √ 2n, which follows from the result by Dujmović and Wood [START_REF] Vida | Three-dimensional upward grid drawings of graphs[END_REF] that tn(G) ≤ 5d √ 2n for every d-degenerate (ii) graph G. Thus for large ∆, the lower bound in Theorem 2 tends toward this upper bound.

Proof of Theorem 1

The proof of Theorem 1 is modelled on a similar proof by Barát et al. [START_REF] Át | Bounded-degree graphs have arbitrarily large geometric thickness[END_REF]. Basically, we show that there are more ∆-regular graphs than graphs with bounded queue-number. The following lower bound on the number of ∆-regular graphs is a corollary of more precise bounds due to Bender and Canfield [START_REF] Bender | The asymptotic number of labeled graphs with given degree sequences[END_REF], Wormald [START_REF] Wormald | Some problems in the enumeration of labelled graphs[END_REF], and McKay [START_REF] Mckay | Asymptotics for symmetric 0-1 matrices with prescribed row sums[END_REF]; see [START_REF] Át | Bounded-degree graphs have arbitrarily large geometric thickness[END_REF].

Lemma 1 ([2, 22, 31]) For all integers ∆ ≥ 1 and for sufficiently large n ≥ n(∆), the number of labelled simple ∆-regular n-vertex graphs is at least

n 3∆ ∆n/2
It remains to count the graphs with bounded queue-number. We will need the following lemma, which was previously known only for loopless graphs.

Lemma 2 ([8]

) Every n-vertex queue has at most 2n -1 edges.

(i) A converse result in fact holds. Dujmović et al. [START_REF] Vida Dujmovi | Track layouts of graphs[END_REF] proved that track-number is bounded by a function of queue-number. In particular, tn(G) ≤ 4 qn(G) • 4 qn(G)(2 qn(G)-1)(4 qn(G)-1) for every graph G. Let g(n) be the number of queues on n vertices. For our purposes it suffices to show that g(n) ≤ c n . While such a bound can be concluded from the work of Klazar [START_REF] Martin Klazar | Counting pattern-free set partitions. II. Noncrossing and other hypergraphs[END_REF], who described a generating function for g(n) with rough asymptotic analysis, we include a different and simpler proof for the sake of completeness. It is similar to a proof of a more general result by Klazar [START_REF] Martin Klazar | The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture[END_REF]; also see [START_REF] Tardos | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF][START_REF] Ábor Tardos | On 0-1 matrices and small excluded submatrices[END_REF] for other related and more general results. Lemma 3 g(n) ≤ c n for some absolute constant c.

Proof: Say G is an n-vertex queue. Let G ′ be an ordered 2n-vertex graph obtained by the following doubling operation. For every edge vw of G, add to G ′ a non-empty set of edges between {2v -1, 2v} and {2w -1, 2w}, no pair of which are nested. If v = w then there are 11 possible ways to do this, as illustrated in Figure 1, and if v = w then there are 7 possible ways to do this, as illustrated in Figure 2. Now G has at most 2n-1 edges by Lemma 2. Thus at most 11 2n-1 queues on 2n vertices can be obtained from G by doubling. On the other hand, every 2n-vertex queue can be obtained from some n-vertex queue by doubling. To see this, merge every second pair of vertices, introduce a loop between merged vertices that are adjacent, and replace any resulting parallel edges by a single edge. No two edges are nested in the obtained graph. Hence g(2n)

≤ 11 2n-1 • g(n). It follows that g(n) ≤ 11 2n . ✷ 2 v -1 2 v 2 w -1 2 w
Fig. 1: The 11 possible ways to add a non-empty set of non-nested edges between {2v -1, 2v} and {2w -1, 2w}.

Lemma 3 implies:

Corollary 1 The number of k-queues on n vertices is at most c kn for some absolute constant c.

It is easily seen that Lemma 1 and Corollary 1 imply a lower bound of c(∆/2 -1) log n on the queuenumber of some ∆-regular n-vertex graph. To improve this logarithmic bound to polynomial, we now give a more precise analysis of the number of k-queues that also accounts for the number of edges in the graph. Let g(n, m) be the number of queues on n vertices and m edges.

Lemma 4 g(n, m) ≤ n 2m • c 2m , if m ≤ n 2 c n , if m > n 2 ,
for some absolute constant c.

Proof: By Lemma 3, we have the upper bound of c n regardless of m. Suppose that m ≤ n 2 . An m-edge graph has at most 2m vertices of non-zero degree. Thus every n-vertex m-edge queue is obtained by first choosing a set S of 2m vertices, and then choosing a queue with |S| vertices. The result follows. ✷

Let g(n, m, k) be the number of k-queues on n vertices and m edges.

Lemma 5 For all integers k such that 2m n ≤ k ≤ m, g(n, m, k) ≤ ckn m 2m
for some absolute constant c.

Proof: Fix non-negative integers m 1 ≤ m 2 ≤ • • • ≤ m k such that i m i = m.
) ≤ j i=1 n 2m i c 2mi (c n ) k-j . Now j i=1 m i ≤ m -1 2 (k -j)n. Thus g(n; m 1 , m 2 , . . . , m k ) ≤ j i=1 n 2m i c 2m-(k-j)n c (k-j)n ≤ c 2m k i=1 n 2m i .
We can suppose that k divides 2m. It follows (see [START_REF] Át | Bounded-degree graphs have arbitrarily large geometric thickness[END_REF]) that

g(n; m 1 , m 2 , . . . , m k ) ≤ c 2m n 2m/k k .
It is well known [18, Hence k ≥ √ ∆n 1/2-1/∆ /( √ 3c). ✷

k + m -1 m < 2m m < 2

  (ii) A graph G is d-degenerate if every subgraph of G has a vertex of degree at most d.Proof: If v + w = x + y for two distinct edges vw and xy, then vw and xy are nested. No two edges are nested in a queue. The result follows since 2 ≤ v + w ≤ 2n. ✷

Fig. 2 :

 2 Fig. 2: The 7 possible ways to add a non-empty set of edges on 2v -1 and 2v.

✷Corollary 2

 2 2m . Hence g(n, m, k) ≤ 2 2m c e kn 2m 2m . Every ordered graph on n vertices is isomorphic to at most n! labelled graphs on n vertices. Thus Lemma 5 has the following corollary. For all integers k such that 2m n ≤ k ≤ m, the number of labelled n-vertex m-edge graphs with queue-number at most k is at most ckn m 2m n!, for some absolute constant c. ✷ Proof of Theorem 1: Let k be the minimum integer such that every simple ∆-regular graph with n vertices has queue-number at most k. Thus the number of labelled simple ∆-regular graphs on n vertices is at most the number of labelled graphs with n vertices, 1 2 ∆n edges, and queue-number at most k. By Lemma 1 and Corollary 2,

  Let g(n; m 1 , m 2 , . . . , m k ) be the number of k-queues G on n vertices such that there is a partition {E 1 , E 2 , . . . , E k } of E(G), and each G[E i ] is a queue with |E i | = m i . Then g(n; m 1 , m 2 , . . . , m k ) ≤

	k
	g(n, m i ).
	i=1
	Now m 1 ≤ n 2 , as otherwise m > kn 2 ≥ m. Let j be the maximum index such that m j ≤ n 2 . By Lemma 4,
	g(n; m 1 , m 2 , . . . , m k

  , m 2 , . . . , m k ),where the sum is taken over all non-negative integersm 1 ≤ m 2 ≤ • • • ≤ m k such that i m i = m.The number of such partitions[START_REF] Stasys Jukna | Extremal combinatorics: with applications in computer science[END_REF] Proposition 1.4] is at most

	Proposition 1.3] that n t < (en/t) t . Thus with t = 2m/k we have
	g(n; m 1 , m 2 , . . . , m k ) <	c e kn 2m	2m	.
	Clearly
	g(n, m, k) ≤	m1,...,m k	g(n; m 1

Acknowledgements

Thanks to Martin Klazar who found an error in an early draft of this paper.

† Research supported by a Marie Curie Fellowship from the European Commission under contract MEIF-CT-2006-023865, and by the projects MEC MTM2006-01267 and DURSI 2005SGR00692. 1365-8050