PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 67(81) (2000), 1–6

THE β-POLYNOMIALS OF COMPLETE GRAPHS ARE REAL

Xueliang Li, Ivan Gutman and Gradimir V. Milovanović

Communicated by Slobodan Simić

Abstract. A polynomial is said to be real if all its zeros are real. It has been conjectured that the β-polynomials of all graphs are real. In this paper we show that the conjecture is true for complete graphs. In fact, we obtain a more general result, namely that certain linear combinations of Hermite polynomials are real.

Introduction

Polynomials whose all zeros are real-valued numbers are said to be real. Several graphic polynomials are known to be real; among them the matching polynomial plays a distinguished role [3,4,9].

Let G be a graph on n vertices. The matching polynomial of G is defined as [3]:

α(G, x) = ∑_{k≥0}(−1)^{k} m(G, k) x^{n−2k}

where m(G, k) is the number of k-matchings of G, i.e., the number of ways in which k mutually non-touching edges are selected in G; m(G, 0) = 1 and m(G, 1) = number of edges of G.

The fact that for all graphs, all zeros of the matching polynomial are real-valued has been first established by Heilmann and Lieb [9]; see also [3,4].

Let C be a circuit contained in the graph G. The subgraph obtained by deleting the vertices of C from G is denoted by G ∖ C. The number of vertices of C will be denoted by m. Then G ∖ C possesses n − m vertices.

If C is a Hamiltonian circuit, i.e., if m = n then, by definition, α(G ∖ C, x) ≡ 1 . In certain considerations in theoretical chemistry [2,11,14,15], graphic polyno-

mials β(G, C, x) are encountered, defined as

(1)  β(G, C, x) = α(G, x) − 2 α(G ∖ C, x)

1991 Mathematics Subject Classification. Primary 05C50, 05C70, 33C45.

and

(2)  β(G, C, x) = α(G, x) + 2 α(G ∖ C, x)

These have been named [2] circuit characteristic polynomials, but in this work we call them simply β-polynomials. Formula (1) is used in the case of so-called Hückeltype circuits whereas formula (2) for so-called Möbius-type circuits; for more details see [14].

For the success of the chemical theory in which β-polynomials occur, it is essential that these polynomials are real. Already in the first paper devoted to this topic [2], Aihara mentioned that the zeros of the β-polynomials were real-valued, but gave no argument to support his claim. In the meantime, for a number of classes of graphs it was shown that β(G, C, x) is indeed a real polynomial [5,6,8,11,12,13,15]. In addition to this, by means of extensive computer searches not a single graph with non-real β-polynomial could be detected. The following conjecture has been put forward [5,6,8]:

Conjecture. For any circuit C contained in any graph G, the β-polynomials β(G, C, x), equations (1) and (2), are real.

Up to the present moment this conjecture has neither been proved nor disproved (although a prize is offered for its solution [8]). On the other hand, many results, corroborating its validity, have been obtained. Thus, in particular, β(G, C, x) has been shown to be real for: − unicyclic graphs [8]; − bicyclic graphs [15]; − graphs in which no edge belongs to more than one circuit [15]; − graphs without 3-matchings (m(G, 3) = 0) [11]; − several (but not all) classes of graphs without 4-matchings (m(G, 4) = 0) [12]. Note that the aforementioned graphs have comparatively few edges. A natural

question is whether or not the conjecture is true for dense graphs. The extreme case in this direction is the complete graph. In this work we show that the conjecture is obeyed by complete graphs.

The main result

Theorem 1. Let K_{n} be the complete graph on n vertices and C any of its circuits. Then β(K_{n}, C, x) , equations (1), (2), is a real polynomial.

Instead of Theorem 1 we demonstrate the validity of a stronger result, namely Theorem 2. In order to state it we need some preparations.

If C is a circuit on m vertices, then K_{n} ∖ C = K_{n−m}, implying that

(3)  β(K_{n}, C, x) = α(K_{n}, x) ± 2 α(K_{n−m}, x)

Now, a well-known result from the theory of matching polynomial is [4,7,9,10]:

(4)  α(K_{n}, x) = He_{n}(x)

THE β-POLYNOMIALS OF COMPLETE GRAPHS ARE REAL 3

where He_{n} is one of the standard forms of the Hermite polynomial [1, p. 778]. Such (monic) Hermite polynomials are orthogonal on (−∞, +∞) with respect to the weight function e^{−x^{2}/2} .

Bearing in mind equations (4) and (4) we define a polynomial

(5)  β(n, m, t, x) = He_{n}(x) + t He_{n−m}(x),

where 1 ≤ m ≤ n and t is a real number. Clearly, for n ≥ 3 , |t| = 2 and 3 ≤ m ≤ n, equation (5) is the β-polynomial of the complete graph on n vertices, pertaining to a circuit with m vertices.

Theorem 2. For all (positive integer) values of n, for all m = 1, 2,…, n and for |t| ≤ n − 1 the polynomial β(n, m, t, x) , equation (5), is real.

Obviously, Theorem 1 is a special case of Theorem 2. Therefore in what follows we proceed towards proving Theorem 2. It should be noted that the right-hand side of equation (5) is a sort of linear combination of Hermite polynomials.

Preparations

Some well known properties [1] of the Hermite polynomials are summarized in Lemma 1.

Lemma 1. (i) The Hermite polynomials He_{n}(x) satisfy the three-term recurrence relation

He_{n}(x) = x He_{n−1}(x) − (n − 1) He_{n−2}(x);

(ii) All zeros of He_{n}(x) are real and distinct;

(iii)

\frac{d}{dx}He_{n}(x) = n He_{n−1}(x)

and hence, He_{n}(x) has a local extreme x_{i} if and only if He_{n−1}(x_{i}) = 0 . So, the extremes of He_{n}(x) are distinct.

Throughout this paper x_{1}, x_{2},…, x_{n−1} denote the distinct zeros of He_{n−1}(x) . From equation (4) and Theorem 7 of [4], we have

Lemma 2. |x_{i}| < 2 \sqrt{n − 3} holds for all i = 1, 2,…, n − 1 and n ≥ 4 .

Lemma 3. If for all i = 1, 2,…, n − 1 , the sign of

β(n, m, t, x_{i}) = He_{n}(x_{i}) + t He_{n−m}(x_{i})

is the same as that of He_{n}(x_{i}) , then β(n, m, t, x) is real.

Proof. From Lemma 1 (iii), we have that x_{i}, i = 1, 2,…, n−1 are the extremes of He_{n}(x) . Since He_{n}(x) does not have multiple zeros (Lemma 1 (ii)), we know that He_{n}(x_{i}) ≠ 0 for all i = 1, 2,…, n − 1 , and that He_{n}(x_{i}) and He_{n}(x_{i+1}) have different signs, i = 1, 2,…, n − 2 .

From the definition of β(n, m, t, x) and the condition of Lemma 3, we deduce that β(n, m, t, x) has at least as many real zeros as He_{n}(x) , that is at least n real zeros. On the other hand the degree of β(n, m, t, x) is n. □

Lemma 4. If |He_{n}(x_{i})| > (n − 1) |He_{n−m}(x_{i})| for all i = 1, 2,…, n − 1 , then β(n, m, t, x) is real for |t| ≤ n − 1 .

Proof. Since |He_{n}(x_{i})| > (n − 1) |He_{n−m}(x_{i})| ≥ |t| |He_{n−m}(x_{i})| for all i = 1, 2,…, n − 1 , the sign of β(n, m, t, x_{i}) = He_{n}(x_{i}) + t He_{n−m}(x_{i}) depends only on the sign of He_{n}(x_{i}) . Lemma 4 follows from Lemma 3. □

Proof of Theorem 2

Bearing in mind that He_{n−1}(x_{i}) = 0 , from Lemma 4 we directly get

Lemma 5. The polynomial β(n, 1, t, x) is real for n ≥ 1 and any real value of the parameter t.

Lemma 5 implies the validity of Theorem 2 for m = 1 . What remains is to consider the case m ≥ 2 . Therefore, in what follows it will be assumed that 2 ≤ m ≤ n.

Define the auxiliary quantities a_{n,m} as

(6)  a_{n,m} = max_{1≤i≤n−1} |\frac{He_{n−m}(x_{i})}{He_{n}(x_{i})}|

Because of Lemma 5, if

(7)  a_{n,m} ≤ \frac{1}{n − 1}

then β(n, m, t, x) is real for |t| ≤ n − 1 . Therefore, in order to complete the proof of Theorem 2 we only need to verify the inequality (7).

Using the well-known three-term recurrence relation for the Hermite polynomials (Lemma 1), equation (6) reduces to

a_{n,m} = \frac{1}{n − 1} max_{1≤i≤n−1} |\frac{He_{n−m}(x_{i})}{He_{n−2}(x_{i})}| = \frac{1}{(n − 1)(n − 2)} max_{1≤i≤n−1} |\frac{x_{i} He_{n−m}(x_{i})}{He_{n−3}(x_{i})}|

and we conclude immediately that

a_{n,1} = 0 , a_{n,2} = \frac{1}{n − 1} (n ≥ 2) ,

and

a_{n,3} = \frac{1}{(n − 1)(n − 2)} max_{1≤i≤n−1} |x_{i}| \{ \begin{matrix}= \frac{1}{n − 1} , & n = 3, \\ < \frac{2 \sqrt{n − 3}}{(n − 1)(n − 2)} ≤ \frac{1}{n−1} , & n ≥ 4. \end{matrix}

Note that the relation a_{n,1} = 0 provides another proof of Lemma 5. The upper bound for a_{n,3} follows from Lemma 2.

The case when n ≥ m ≥ 4 can be verified using a result of Turán [17] (see also [16]). Namely, under the condition

∑_{k=0}^{n−2} k! c_{k}^{2} < (n − 1)! c_{n}^{2} ,

Turán proved that the polynomial P (z) = ∑_{k=0}^{n} c_{k} He_{k}(z) has n distinct real zeros.

Considering the β-polynomial given by (5), we conclude that it has all real zeros if |t| < \sqrt{(n − 1)!/(n − m)!} . On the other hand, it is easily verified that for n > m ≥ 4 the expression \sqrt{(n − 1)!/(n − m)!} is greater than n − 1 .

Notice that a_{4,4} = 1/3 . By this, the proof of Theorem 2 has been completed. □

Acknowledgements. This work was partially supported by the Euler Institute of Discrete Mathematics and Its Applications while one of the authors (X. L.) visited the Department of Applied Mathematics, University of Twente, The Netherlands, and by the Ministry of Science and Technology of Serbia, grant number 04M03. The authors are grateful to Dr. A. A. Jagers for useful suggestions.

References

[1] M. Abramowitz, I. A. Stegun, Handbook of Mathematical Functions, Dover, New York, 1972.

[2] J. Aihara, Resonance energies of benzenoid hydrocarbons, J. Am. Chem. Soc. 99 (1977) 2048– 2053.

[3] D. Cvetković, M. Doob, I. Gutman, A. Torgašev, Recent Results in the Theory of Graph Spectra, North–Holland, Amsterdam, 1988.

[4] C. D. Godsil, I. Gutman, On the theory of the matching polynomial, J. Graph Theory 5 (1981) 137–144.

[5] I. Gutman, A contribution to the study of real graph polynomials, Publ. Elektrotehn. Fak. (Beograd) Ser. Mat. 3 (1992) 35–40.

[6] I. Gutman A real graph polynomial?, Graph Theory Notes New York 22 (1992) 33–37.

[7] I. Gutman, D. M. Cvetković Relations between graphs and special functions, Coll. Sci. Papers Fac. Sci. Kragujevac 1 (1980) 101–119.

[8] I. Gutman, N. Mizoguchi, A property of the circuit characteristic polynomial, J. Math. Chem. 5 (1990) 81–82.

[9] O. J. Heilmann, E. H. Lieb, Theory of monomer–dimer systems, Commun. Math. Phys. 25 (1972) 190–232.

[10] H. Hosoya, Graphical and combinatorial aspects of some orthogonal polynomials, Nat. Sci. Repts. Ochanomizu Univ. 31 (1981) 127–138.

[11] M. Lepović, I. Gutman, M. Petrović, N. Mizoguchi, Some contributions to the theory of cyclic conjugation, J. Serb. Chem. Soc. 55 (1990) 193–198.

[12] M. Lepović, I. Gutman, M. Petrović, A conjecture in the theory of cyclic conjugation and an example supporting its validity, Commun. Math. Chem. (MATCH) 28 (1992) 219–234.

[13] X. Li, B. Zhao, I. Gutman, More examples for supporting the validity of a conjecture on β-polynomial, J. Serb. Chem. Soc. 60 (1995) 1095–1101.

[14] N. Mizoguchi, Unified rule for stability of Hückel–type and Möbius–type systems, J. Phys. Chem. 92 (1988) 2754–2756.

[15] N. Mizoguchi, Circuit resonance energy. On the roots of circuit characteristic polynomial, Bull. Chem. Soc. Japan 63 (1990) 765–769.

[16] G. Schmeisser, Inequalities for the zeros of an orthogonal expansion of a polynomial, in: G. V. Milovanović (Ed.), Recent Progress in Inequalities, Kluwer, Dordrecht, 1998, pp. 381–396.

[17] P. Turán, To the analytic theory of algebraic equations, Izv. Mat. Inst. Bulgar. Akad. Nauk 3 (1958) 123–137.

Xueliang Li Department of Applied Mathematics Northwestern Polytechnical University X’ian, Shaanxi 710072 P.R. China

iamlxl@nwpu.edu.cn

Ivan Gutman

Prirodno-matematički fakultet 34001 Kragujevac, p.p. 60 Yugoslavia

                                       gutman@knez.uis.kg.ac.yu

Gradimir V. Milovanović Elektronski fakultet 18001 Niš, p.p. 73 Yugoslavia

grade@gauss.elfak.ni.ac.yu

(Received 20 02 1998) (Revised 12 10 1999)