PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 90(104) (2011), 99–110 DOI: 10.2298/PIM1104099D

SPECTRA AND GRAPH COMPARISON

Charles Delorme

Communicated by Slobodan K. Simić

Abstract. We give some inequalities relating the number of edges that two graphs of the same order may have in common with their degree sequences and their spectra. We then give some examples and related inequalities, and present applications to independence number and coloration.

1. Introduction

We consider graphs (or directed graphs). Taking two of them with the same number of vertices, we want to find how many common edges (or arcs) they may have. In other words, any bijection between the two sets provide a set of common edges, or arcs, and we want to compute its cardinality (that clearly may depend on the bijection), or at least give bounds. A generalization comes to mind: with weighted edges or arcs, how to bound the sum of the products of the weights on common edges?

We indicate bounds from the degree sequences. Of course, since nonisomorphic graphs with the same degree sequence exist, the bound may differ from the actual value. We indicate some results from spectra. Of course, these results cannot say everything, since there exist pairs of graphs with the same spectrum. We then apply the results to give upper bounds on the independence number and lower bounds on the chromatic number of a graph; these quantities have been related to spectra by many authors.

Good bases on these questions can be found in Haemers [3], Godsil [2], Karger, Motwani and Sudan [5] among many other works.

2. Inequalities

We give here some inequalities about finite real sequences.

Lemma 2.1. Let a_{i}, 1 ⩽ i ⩽ n, and b_{i}, 1 ⩽ i ⩽ n be two nondecreasing sequences of real numbers. Then for any permutation σ of {1, …, n} we have

2010 Mathematics Subject Classification: 05C50, 05C07.

Key words and phrases: degree sequences, spectra, graph morphisms.

∑_{1⩽i⩽n} a_{i}b_{i} ⩾ ∑_{1⩽i⩽n} a_{i}b_{σ(i)}
∑_{1⩽i⩽n} min(a_{i}, b_{i})⩾ ∑_{1⩽i⩽n} min(a_{i}, b_{σ(i)} )
∑_{1⩽i⩽n} a_{i}b_{n+1−i} ⩽ ∑_{1⩽i⩽n} a_{i}b_{σ(i)}

Proof. If b_{σ(j)} < b_{σ(i)} and a_{i} < a_{j}, then a_{i}b_{σ(i)} + a_{j} b_{σ(j)} < a_{i}b_{σ}(j) + a_{j} b_{σ(i)} and min(a_{i}, b_{σ(i)} ) + min(a_{j} , b_{σ(j)} ) ⩽ min(a_{i}, b_{σ(j)} + min(a_{j} , b_{σ(i)} ). Thus the permutation σ ∘ τ, where τ is the transposition swapping i and j gives two larger sums than σ. Since any permutation is a product of transpositions, we see that the maximum is obtained when σ is the identity. The last inequality is easily deduced from the first one, using the sequences a_{i} and −b_{i}. □

3. Tools from degree sequences

We consider only simple graphs, without loops.

Clearly the number of common edges in graphs on n vertices with sizes m_{1} and m_{2} is at most inf\{m_{1}, m_{2}\}, and at least sup\{0, m_{1} + m_{2} − \frac{1}{2}n(n − 1)\}, if the sets of vertices are equal. But this does not take at all into account the structure of the graphs. A step to the use of the structure is the consideration of degree sequences.

Proposition 3.1. Let G and H be two graphs with n vertices. If d_{1}, d_{2}, …, d_{n} is the (increasing) sequence of degrees of G and e_{1}, e_{2}, …, e_{n} the one of H, then the number of common edges is at least \frac{1}{2} ∑ _{1⩽i⩽n} sup\{0, d_{i} + e_{n+1−i} − (n − 1)\} and at most \frac{1}{2} ∑ _{1⩽i⩽n} inf\{d_{i}, e_{i}\}.

Proof. If we label the vertices of G and those of H with the integers from 1 to n such that the degrees are increasing, and choose a bijection ϕ : V (G) → V (H) between their sets of vertices, we obtain a table of pairs of degrees, say d(v) = d_{G}(v) and e(v) = d_{H} (ϕ(v)). For each vertex v of G there are at most min(d(v), e(v)) common edges incident to vertex v. Thus there are at most \frac{1}{2} ∑ _{v∈V (G)} min(d(v), e(v)) edges in common.

According to Lemma 2.1, we see that the maximum number of common edges is at most \frac{1}{2} ∑ _{1⩽i⩽n} inf\{d_{i}, e_{i}\}.

To obtain the other bound, we may consider that the number of edges common to G and H plus the number of edges common to G and the complement of H is the number of edges of G. □

Clearly this technique does not distinguish graphs with the same degree sequences.

For the two graphs of Figure 1, there is at most 5 edges in common (not 6) and at least 2 (this bound is the actual minimum).

Remark 3.1. The upper bound remains valid for graphs with multiple edges and without loops.

Figure 1. Two graphs with the same degree sequence 3, 3, 2, 2, 2

Similar bounds appear for directed graphs: the number of common arcs of two directed graphs G, H with n vertices is at most ∑ _{1⩽i⩽n} inf{d_{i}^{+} , e_{i}^{+} }, where d_{i}^{+} and e_{i}^{+} are the out-degrees in G and H sorted in increasing order, and also at most ∑ _{1⩽i⩽n} inf{d_{i}^{−} , e_{i}^{−} } (in-degrees).

4. Tools from linear algebra

Our main remark is the following.

Proposition 4.1. Given two graphs G, H with the same set of n vertices, and adjacency matrices A_{G} and A_{H}, the number of edges common to G and H is \frac{1}{2} tr(A_{G}A_{H}).

For directed graphs, the arc from i to j is represented by a 1 in position i, j. The number of common arcs is then tr(A_{G}^{∗}A_{H}),

Proof. The entry ii of the product is just the number of edges common to G and H and incident to vertex i.

A similar observation holds for the arcs of directed graphs. □

Therefore, any information on the trace coming from the spectra or other finer invariants gives information on the number of common edges after a permutation of the vertices. Our main tools will be the inequalities, that can be found in [4].

tr(A) is at most the sum of the singular values of A

the sum of the singular values of AB is at most ∑_{1⩽i⩽n} a_{i}b_{i}

where the a_{i}’s and b_{i}’s are the singular values of the matrices A and B written in increasing order (with enough 0’s added in front).

We recall that the singular values of a real or complex matrix M (not necessarily a square one) are the positive square roots of the eigenvalues of MM^{∗} (or M^{∗}M as well) where^{∗} is the adjunction (transpose and conjugate). See [4, p. 154, eq. 3.1.10a] and [4, p. 177, th. 3.3.14].

For a hermitian-symmetric matrix (in particular for a real symmetric matrix), the singular values are the absolute values of its eigenvalues.

5. Using the tools

Since we are interested in the maximum and minimum traces of AP^{∗}BP, where A and B are the adjacency matrices of two graphs (with the same sets of vertices) and P a permutation matrix, we relax the question with P being now an orthogonal or unitary matrix such that the all-1 column J_{n,1} is preserved, (i.e., P J_{n,1} = J_{n,1} ).

Therefore, we will change the base, with a first new vector collinear to J_{n,1} , in other words, we replace A by A′ = Q^{∗}AQ with Q an orthogonal matrix whose first column is J_{n,1} /\sqrt{n}, and operate a similar replacement for B, and use now instead of the orthogonal P a matrix with first row (1, 0, …., 0) and first column (1, 0, …, 0)^{∗}, the remaining block of Q being an orthogonal or unitary matrix of size (n − 1) × (n − 1).

The upper left entry of A′ is the average d̄ of the entries of A, the end of the first column of A′′satisfies: ∑ _{i=2}^{n} (a′_{i,1} )^{2} is the variance of the sums of entries in the rows of A, that is to say the variance of the out-degrees d_{i}^{+} of the graph represented by A, that is v^{+} = \frac{1}{n} ∑ _{1⩽i⩽n} (d_{i}^{+} )^{2} − d̄^{2}. Similarly, the end of the first row of A′ satisfies: ∑ _{i=2}^{n} (a′_{1,i})^{2} is the variance of the in-degrees d_{i}^{−} .

Thus the trace of A^{∗}B is the sum of four terms, namely • the product of the average in-degrees (or out-degrees as well) of the graphs • the scalar product of the ends of the two first columns, that is between

\sqrt{v^{+} (A)v^{+} (B)} and its opposite

• the scalar product of the ends of the first rows,of A′ and B′, that is between \sqrt{v^{−} (A)v^{−} (B)} and its opposite

• the trace of (A′′)^{∗}(B′′), that is between the sum of products of the singular values of A′′and B′′taken in increasing order and its opposite, where A′′ and B′′are the lower right blocks of size (n − 1) × (n − 1) of A′ and B′.

5.1. Example. Let A be the undirected path on three vertices with matrix

[ \begin{matrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}]

let us use the following orthogonal matrix P

[ \begin{matrix}1/\sqrt{3} & 1/\sqrt{2} & 1/\sqrt{6} \\ 1/\sqrt{3} & 0 & −2/\sqrt{6} \\ 1/\sqrt{3} & −1/\sqrt{2} & 1/\sqrt{6} \end{matrix} ]

Then A′ is the matrix

[ \begin{matrix}4/3 & 0 & −\sqrt{2}/3 \\ 0 & 0 & 0 \\ −\sqrt{2}/3 & 0 & −4/3 \end{matrix} ]

The singular values of the lower right block are 0 and 4/3. Using S = 2/9 + 2/9 + 16/9, the number m of edges that this graph may share with a copy of itself (obviously the actual possible values are 1 and 2 in this case) is bounded by \frac{1}{2}(16/9 − S) and \frac{1}{2}(16/9 + S), which evaluate to −0.22 and 2.

5.2. Example. The directed 4-circuit can be similarly treated with its adjacency matrix A, and the orthogonal matrix P

A = [ \begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{matrix}] P = [ \begin{matrix}1/2 & 1/2 & 1/2 & 1/2 \\ 1/2 & 1/2 & −1/2 & −1/2 \\ 1/2 & −1/2 & 1/2 & −1/2 \\ 1/2 & −1/2 & −1/2 & 1/2 \end{matrix} ]

giving

P^{−1} AP = [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 0 & 0 & −1 \\ 0 & 0 & −1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ]

The singular values of the lower right block are 1, 1, 1.

The star with 3 rays going out of the center gives similarly

A = [ \begin{matrix}0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}]

and with the use of the same orthogonal matrix

P^{−1} AP = [ \begin{matrix}3/4 & −1/4 & −1/4 & −1/4 \\ 3/4 & −1/4 & −1/4 & −1/4 \\ 3/4 & −1/4 & −1/4 & −1/4 \\ 3/4 & −1/4 & −1/4 & −1/4 \end{matrix} ]

The lengths of the end of first row and column (i.e., the standard deviations of the degrees) are \sqrt{3}/4 and 3\sqrt{3}/4, the singular values of the lower right block are 0, 0, 3/4.

Using S = 0 · \sqrt{3}/4 + 0 · 3\sqrt{3}/4 + 1 · 0 + 1 · 0 + 1 · 3/4, the number of common arcs is between 3/4 · 1 − S and 3/4 · 1 + S, these bounds are 0 and 3/2, and the actual number is 1.

6. Optimization

The gap between the lower and upper bounds on the number of common edges comes from the irregularity of degrees, and from the singular values of the lower right block. One may thus try to reduce it by maneuvers that take into account that the adjacency matrices have a null diagonal.

We may for example replace A by A + aI and B by B + bI, where a and b are numbers, and I the identity matrix. The trace of (A+aI)^{∗}(B+bI) is tr(A^{∗}B)+a^{∗}bn.

We may also add in one of the matrices (not both !) a diagonal with null trace; if D is such a diagonal, then (A + aI + D)^{∗}(B + bI) is again tr(A^{∗}B) + a^{∗}bn.

6.1. Example. Taking again the graph K_{1,2} of example 5.1, we replace A by A + (2/3)I. The new matrix A′ is thus

[ \begin{matrix}4/3 + 2/3 & 0 & −\sqrt{2}/3 \\ 0 & 2/3 & 0 \\ −\sqrt{2}/3 & 0 & −2/3 \end{matrix} ] .

The singular values of the lower right block are now 2/3, 2/3, and, setting S = 2/9 + 2/9 + 4/9 + 4/9 = 4/3, the number of common edges is now found to be between \frac{1}{2}(2 · 2 − S − 4/3) and \frac{1}{2}(2 · 2 + S − 4/3), that is to say between 2/3 and 2.

6.2. Example. Taking again the digraphs of example 5.2, adding aI to the matrix A of the circuit and bI to the matrix B of the star, and setting S = a_{1}b_{1} + a_{2}b_{2}+a_{3}b_{3} we have to optimize (1+a)(3/4+b)−4ab+S and (1+a)(3/4+b)−4ab−S, where the a_{i}’s and b_{i}’s are the singular values of

[ \begin{matrix}a & 0 & −1 \\ 0 & a − 1 & 0 \\ 1 & 0 & a \end{matrix} ] and [ \begin{matrix}b − 1/4 & −1/4 & −1/4 \\ −1/4 & b − 1/4 & −1/4 \\ −1/4 & −1/4 & b − 1/4 \end{matrix} ]

in increasing order. Up to order the a_{i}’s are \sqrt{a^{2} + 1} , \sqrt{a^{2} + 1} , |a − 1| and the b_{i}’s are |b|, |b|, |b − 3/4|. Hence the upper bound is minimized for a = 0, b = 0, and then is 3/2, the lower bound is maximized for a = −∞, b = 3/4 and its value is then 3/4. These two bounds suffice to prove that the number of common arcs is 1.

6.3. A poor example. The graph is the directed star with 2 rays coming out of the center and 1 ray in the other direction. The out-degrees are 2,1,0,0, with average 3/4 and variance 11/16, and the in-degrees are 0,1,1,1, with average 3/4 and variance 3/16. We make an orthogonal change of basis with the first vector collinear to J_{n,1} . The lower-right block has singular values 0, \frac{3+\sqrt{41}}{8} , \frac{\sqrt{41}−3}{8} . This graph and a copy of itself have at most ( \frac{3}{4})^{2}+ \frac{11}{16} + \frac{3}{16} +( \frac{3+\sqrt{41}}{8} )^{2}+( \frac{\sqrt{41}−3}{8} )^{2} = 3 arcs in common (this is good) and at least ( \frac{3}{4})^{2} − \frac{11}{16} − \frac{3}{16} − ( \frac{3+\sqrt{41}}{8} )^{2} − ( \frac{\sqrt{41}−3}{8} )^{2} = \frac{−30}{16} ones (this is not very informative), the actual minimum is 0.

7. Graphs

Here the adjacency matrices are symmetric. The singular values are thus the absolute values of the eigenvalues. Thus, we can get without extra computations the upper and lower bounds from the spectra.

Proposition 7.1. Let A and B be two symmetric real matrices with n rows and columns, and null trace. The trace of A^{∗}B is at most ∑ _{1⩽i⩽n} λ_{i}(A)λ_{i}(B), and at least ∑ _{1⩽i⩽n} λ_{i}(A)λ_{n+1−i} (B), where the λ_{i}’s are the eigenvalues in increasing order.

If moreover A and B admit J_{n,1} as an eigenvector, with eigenvalues a and b we have better bounds, namely tr(AB) ⩽ ab + ∑ _{1⩽i⩽n−1} λ_{i}(A′′)λ_{i}(B′′) and tr(AB) ⩾ ab + ∑ _{1⩽i⩽n−1} λ_{i}(A′′)λ_{n−i} (B′′), where A′′and B′′are the restrictions of A and B to the space orthogonal to J_{n,1} .

Proof. Let us add diagonals cI to A and B, with c a large real, such that the eigenvalues of A + cI and B + cI are positive. Then tr(AB) + nc^{2} ⩽ ∑ _{i=1}^{n} (c + λ_{i}(A))(c+λ_{i}(B)) = nc^{2} +∑ _{i=1}^{n} λ_{i}(A)λ_{i}(B), since the traces of cA and cB are null.

If we take apart the subspace of ℝ^{n} generated by J_{n,1} and its orthogonal subspace, the same trick as above is applied. □

Table 1. Petersen graph and the complete bipartite K_{d,10−d}

degrees actual values bounds bounds with diagonal
1, 9  3, 3  1.8, 4.5  3, 3
2, 8  4, 6  3.2, 8  3.2, 8
3, 7  5, 9  4.2, 10.5  4.2, 10.5
4, 6  6, 12  4.8, 12  4.8, 12
5  5,11  5, 12.5  5, 12.5

We get a corollary

Proposition 7.2. Let G and H be two graphs, with adjacency matrices A and B. The number of common edges is at most \frac{1}{2} ∑ _{n=1}^{n} λ_{i}(A)λ_{i}(B). If the graphs are regular, then a lower bound is given by \frac{1}{2}λ_{n}(A)λ_{n}(B) + ∑ _{i=1}^{n−1} λ_{i}(A)λ_{n−i} (B).

Using the separation of the space generated by J_{n,1} and its orthogonal gives

Proposition 7.3. Let G and H be two graphs, with adjacency matrices A and B. Let d̄(G) and d̄(H) their average degrees, v(G) and v(H) the variances of degrees and A′′, B′′ the restrictions to the space orthogonal to J_{n,1} . Then the number of common edges is at most \frac{1}{2}(d̄(G)d̄(H) + 2\sqrt{v(G)v(H)}+ ∑ _{i=1}^{n−1} λ_{i}(A′′)λ_{i}(B′′)) and at least \frac{1}{2}(d̄(G)d̄(H) − 2\sqrt{v(G)v(H)} + ∑ _{i=1}^{n−1} λ_{i}(A′′)λ_{n−i} (B′′)).

7.1. Example. Petersen graph (with spectrum {(−2)^{[4]}, 1^{[5]}, 3}, where bracketed superscripts indicate multiplicities) and K_{d,10−d} (it has e = d(10−d) edges and with spectrum \{−\sqrt{e}, 0^{[8]}, \sqrt{e}\}) have at most 5\sqrt{e}/2 and at least −5\sqrt{e}/2 common edges (quite uninteresting), but if d = 5 the regularity of K_{5,5} allows to increase the lower bound to 5 edges.

The separation of the space generated by J_{10,1} and its orthogonal gives indeed slightly better bounds. The restriction of the adjacency matrix of K_{d,10−d} has spectrum {0^{[8]}, −2d(10 − d)/10}, this last eigenvalue is the opposite of the average degree d̄; the variance is (d − 5)^{2}/25, hence the bounds (3 − (−2))d̄ and (3 − 1)d̄ presented with actual values, in Table 1. This table also gives the results obtained by adding a suitable diagonal of null trace to the adjacency matrix of K_{d,10−d} .

8. Independence number

We may examine a graph G (resp. with weighted edges) with n vertices and the graph H with n vertices, made from a complete subgraph K of order t and n − t isolated vertices. If the number (resp. the sum of weights) of edges common to G and H is more than 0, then G has no independent set with t elements.

8.1. Example. The graph G is Petersen graph, it is regular, has spectrum {(−2)^{[4]}, 1^{[5]}, 3}, and has 15 edges. The graph H, with n = 10, t = 5 has average degree 2. Adding on the diagonal \frac{1}{2} for the 5 vertices in K and \frac{−1}{2} for the other 5 vertices to its adjacency matrix gives the spectrum {(−1/2)^{[8]}, 2} for the restriction. This, provide a lower bound for the number of common edges that is 5/4. Thus Petersen graph has its independence number at most 4 (it is well known that its independence number is 4) and every induced subgraph on 5 vertices has at least 2 edges (this is the actual value).

8.2. Example. The same technique almost proves that the Petersen graph has not two disjoint independent subsets on 4 vertices.

The average degree of a graph H on 10 vertices, made from 2 disjoint 4-cliques and 2 isolated vertices is 2.4. Adding to its diagonal a for vertices in the two cliques and −4a for the other two vertices gives a restriction with spectrum (up to order) {(a−1)^{[6]}, −4a, a+3, −3a+0.6}, the lower bound for the number of edges common to H and the Petersen graph is 0 for 0.2 ⩽ a ⩽ 0.4.

This means that the eigenvector of H, with coordinates −1, 1, 0^{[8]} associated to the eigenvalue 4a should be in the eigenspace of the Petersen graph associated to eigenvalue 1, and this is not the case.

Thus looking more closely at the eigenspaces (not only the eigenvalues) completes the proof.

9. Coloration

To color properly a graph G with at most k colors c_{1}, c_{2}, …, c_{k} occurring n_{1}, n_{2}, …, n_{k} times (with n_{1} + n_{2} + ⋯+ n_{k} = n) is the same thing as to find a subgraph isomorphic to G in the graph obtained from K_{k} by multiplicating its vertices n_{1}, n_{2}, …, n_{k} times, that is to say K_{n_{1} ,n_{2} ,...,n_{k}} ; it also means that it is possible to find a graph K_{n_{1}} ∪ K_{n_{2}} ∪ ⋯∪ K_{n_{k}} with no edge in common with G, while sharing its n vertices.

Thus to show that a graph G has chromatic number larger than t, it suffices for each partition of n in t parts, say n = n_{1}, n_{2}, …, n_{t} to check that K_{n_{1} ,n_{2} ,...,n_{t}} and G have less edges in common than the number of edges of G. It can be done also by checking that the disjoint union of complete graphs K_{n_{1}} , K_{n_{2}} , …, K_{n_{t}} , with the same vertices as G has at least one edge in common with G.

9.1. Example. The graph K_{d,n−d} has spectrum {−u, 0^{[n−2]} , u}, where the eigenvalue u is \sqrt{d(n − d} . Hence a graph G of order n with \frac{1}{2} \sqrt{d(n − d)} (λ_{n}(G) − λ_{1}(G)) < |E(G)| (where |E(G)| is the number of the edges of G) for each value of d from 1 to ⌊n/2⌋ cannot be bipartite (clearly the inequality for d = ⌊n/2⌋ is the strongest one). This happens for example for the Petersen graph, where n = 10, λ_{1} = −2, λ_{10} = 3.

Of course, this could be improved a bit with the mechanism involving J_{n,1} , the average degree is d̄= \frac{2}{n} d(n − d) and the variance of degrees is \frac{1}{n^{2}} (n − d)d(n − 2d)^{2} and the spectrum of the restriction to the orthogonal of J_{n,1} is {0^{[n−2]} , −d̄}.

9.2. Example. We prove that the circulant graph G_{8} where the vertices are labeled with the elements of ℤ/8ℤ, each vertex x being adjacent to x ± 1 and x ± 2, cannot be colored with 3 colors. The graph is 4-regular, it has 16 edges, its spectrum is \{(−2)^{[2]}, (−\sqrt{2})^{[2]}, 0, \sqrt{2}^{[2]}, 4\}. See Figure 2. The graph H, that is K_{n_{1} ,n_{2} ,n_{3}} with n_{1} +n_{2} +n_{3} = 8 and gives (with just the separation of J_{8,1}) bounds, Table 2. Cutting 8 into 3 positive integers

[3, 3, 2] 15.75 [3, 4, 1] 14.25 [2, 4, 2] 15
[2, 5, 1] 12.75 [1, 6, 1] 9.75

Figure 2. Three graphs with χ > 3

Table 3. Cutting 7 into 3 positive integers

G_{7}  G_{7a}  G_{7}  G_{7a}
[3, 3, 1] 18.625 26.110 [3, 2, 2] 19.867 27.504
[2, 4, 1] 17.384 24.345 [1, 5, 1] 13.658 19.115

all smaller than 16, on the number of properly colored edges, (Table 2) so that the graph is not 3-colorable.

9.3. Example. The same simple technique is not sufficient for the circulant graph G_{7}, where the vertices are labeled with the elements of ℤ/7ℤ, each vertex x being adjacent to x ± 1 and x ± 2. The graph is 4-regular, it has 14 edges, its spectrum is {(−2.2)^{[2]}, −(−0.55)^{[2]}, 0.80^{[2]}, 4}, and the combination 7 = 3 + 2 + 2 gives average degree 32/7, and eigenvalues of restriction {−2.6, −2, 0^{[3]}, 4.6}, and we see \frac{1}{2}(4 · 4.6 + (−2.2)(−2.6 − 2)) > 14. However, one can check that replacing the edges by weighted edges (weight 1 for the edges {x, x + 2} and 2 for the edges {x, x + 1}) we get a regular graph. See Figure 2.

Its spectrum is {(−2.69)^{[2]}, (−2.35)^{[2]}, 2.04^{[2]}, 6}. It appears that the total weight of edges inside K_{n_{1} ,n_{2} ,n_{3}} with n_{1} + n_{2} + n_{3} = 7 is less than the total weight (namely 21) of the edges of G (see Table 3).

Thus the graph is not 3-colorable.

9.4. Example. Giving the indicated weights to the 11 edges the graph on 7 vertices (Figure 2) we have the spectrum {−.2.257, (−1.707)^{[3]}, 0.828, 2.55, 4}, hence the upper bounds in Table 3. Since they are all < 28, the graph has its chromatic number at least 4. By the way, it is a subgraph of the preceding graph G_{7}.

10. Morphisms

Finding a morphism from a graph G to a graph H is embedding the graph G in a graph derived from H by multiplying some vertices by numbers that represent the cardinality of the fibres.

Figure 3. Two multiples of C_{5}

Table 4. Possible types of surjection and the resulting upper bounds

[2, 2, 2, 2, 2] 13.70 [3, 2, 2, 2, 1] 13.28 [3, 2, 2, 1, 2] 13.56
[3, 3, 2, 1, 1] 13.85 [3, 3, 1, 2, 1] 13.70 [3, 1, 3, 1, 2] 12.06
[3, 2, 3, 1, 1] 12.93 [4, 3, 1, 1, 1] 13.81 [4, 1, 3, 1, 1] 11.24
[4, 2, 2, 1, 1] 13.07 [4, 2, 1, 1, 2] 13.81 [4, 2, 1, 2, 1] 13.13
[4, 1, 2, 2, 1] 11.75
[5, 2, 1, 1, 1] 13.04 [5, 1, 2, 1, 1] 11.41 [6, 1, 1, 1, 1] 11.44

10.1. Example. The Petersen graph has spectrum {(−2)^{[4]}, 1^{[5]}, 3}.

Let us show first that it has no morphism towards C_{5} with all fibres of cardinality 2. The multiplied graph obtained from C_{5} has eigenvalues 0 (5 times) and the doubles of the eigenvalues of C_{5}. We thus have the majoration of the number of common edges m ⩽ \frac{1}{2}(−2 · 4 · c_{2} − 2 · 4 · c_{2} + 1 · 4 · c_{1} + 1 · 4 · c_{1} + 3 · 4), where c_{1} = cos \frac{2π}{5} and c_{2} = cos \frac{4π}{5} , that is m ⩽ 13.71 < 15. Figure 3 shows the graphs derived from C_{5} by multiplication by [2, 2, 2, 2, 2] and [4, 1, 2, 2, 1].

Up to symmetry of C_{5}, there are 16 kinds of surjective mappings to C_{5}, none of them is a morphism (see table 4), and the nonsurjective ones cannot be morphisms, since the Petersen graph has no morphism to a bipartite graph.

Of course, since the independence number of the Petersen graph is 4, the last line of Table 4 was not useful.

11. Relaxation of morphisms

In order to avoid a lengthy enumeration of cases, one could replace morphisms from a graph G to a graph H on k vertices and the comparison of G to the various graphs H′ by the comparison between the matrix A of G and P^{∗}BP, where B is the adjacency matrix of H and P is a matrix with n columns and k rows, such that the columns are orthogonal and the sum of squares of the entries in each row is 1. The usual morphisms correspond to the matrices of that kind, with furthermore entries 1 or 0 only.

However, the search for extrema is not made easier, because the function obtained has in general no convexity with respect to the sums of squares in the rows of P.

Table 5. Bounds for well-colored edges in K_{3,3}

p, q  0, 0 1, 1 1.5, 1.5 2, 2 2.5, 2.5 3, 3 1, 2
without  0 8.61 9.27  9  9.46  9 9.37
with  0 7.5  9  9  9.37  9 9.15
actual maximum 0  6  8  9  9

11.1. Example. The coloration of G of order n with 3 colors can be approached by the comparison of G and a matrix P^{∗}BP whose n eigenvalues are the solutions of s^{3} − (pq + qr + pr)s − 2pqr with p + q + r = n, and n − 3 times 0, thus μ_{n} > 0, μ_{1} ⩽ μ_{2} ⩽ 0 and μ_{1} + μ_{2} + μ_{n} = 0

But the bound made from a sum of products of sorted eigenvalues, that we have already used, is not convex in general with respect to the values p, q, r.

Indeed for G isomorphic to the K_{3,3}, (spectrum {−3, 0^{[4]}, 3}), we have the upper bounds of the maximum number of properly colored edges with p, q, r = 6 − p − q (with or without separation) and the actual values (for p, q, r integers of course) in Table 5.

12. Test for the k-colorability

We have however a positive result for k-colorability.

Proposition 12.1. If the k − 1 smallest eigenvalues λ_{1}(G), …, λ_{k}(G) of G are equal and \frac{(k−1)n}{2k} (λ_{n} − λ_{1}) is less than the number of edges of G (or the sum of their weights, if they bear positive weights), then G is not k-colorable.

This will be a consequence of the lemma

Lemma 12.1. Let F be the product of the diagonal matrix diag(p_{1}, p_{2}, …, p_{k}), where the p_{i}’s are positive, and the matrix J_{k,k} − I_{k}. Then F has 1 positive and k − 1 negative eigenvalues, and the maximal value is at most \frac{k−1}{k} ∑ _{i=1}^{k} p_{i}, and at least the geometric mean of the p_{i}’s, with equality if the p_{i}’s are all equal,

Proof. The characteristic polynomial of F is P (X) = X^{k} −∑ _{i=1}^{k−1} X^{k−i} t(i)σ_{i}, where σ_{i} is the elementary symmetric polynomial in the p_{i}’s, and t(i) the difference (with appropriate sign) of the number of even and odd derangements of i elements. For example t(2) = 1 since there is one odd and no even derangement, t(3) = 2 since there are two even and no odd derangement, t(4) = 3 (6 odd and 3 even derangements) and so on.

Clearly, if all p_{i}’s are equal to p, then P (X) = (X − (k − 1)p)(X + p)^{k−1} . Since σ_{i} is then \binom{k}{i}p^{i}, it can be seen that t(i) = i − 1, since the coefficient of X^{k−i} is p^{i} \binom{k−1}{k−i} − (k − 1)\binom{k−1}{k−i−1} = (i − 1)\binom{k}{k−i}.

Now the p_{i}’s are all positive. If p_{i} and p_{j}, with p_{i} ≠ p_{j} are both replaced by (p_{i}+ p_{j})/2, each σ_{i} increases except for σ_{1} that is unchanged, and P (\frac{k−1}{k} σ_{1}) decreases. Since it is null if the p_{i}’s are all equal, it is positive in the other case. We observe that the matrix F is similar to diag(\sqrt{p_{1}}, …, \sqrt{p_{k}})(J_{k,k} − I_{k}) diag(\sqrt{p_{1}}, …, \sqrt{p_{k}}), and has therefore k − 1 negative and one positive eigenvalue. Thus the highest eigenvalue of P is at most \frac{k−1}{k} σ_{1}.

On the other hand, the inequality between arithmetic and geometric means implies σ_{i} ⩾ \binom{k}{i}g^{i}, and thus P ((k − 1)g) ⩽ 0, and the highest root of P is at least g. □

By the way, the Rayleigh principle gives other lower bounds for this positive eigenvalue, one is \frac{2}{k} ∑ _{1⩽i<j⩽k} \sqrt{p_{i}p_{j}} (higher than g because of the inequality between arithmetic and geometric mean), and another one is 2σ_{2}/σ_{1} (i.e., the average degree of K_{p_{1} ,...,p_{k}} ) that is sometimes above and sometimes below \frac{2}{k} ∑_{1⩽i<j⩽k} \sqrt{p_{i}p_{j}}.

One may note that ∑ _{1⩽i⩽n} λ_{i}μ_{i} ⩽ λ_{n}μ_{n} + λ_{1}(μ_{1} + ⋯ μ_{k−1} ) = (λ_{n} − λ_{1})μ_{n} ⩽

(λ_{n} − λ_{1})\frac{(k−1)n}{k} , hence a (weaker) lower bound for the chromatic number χ of G, namely χ ⩾ \frac{λ_{n} −λ_{1}}{λ_{n} −λ_{1} −d̄} , where d̄ is the average degree of G. If G is regular, this is just χ ⩾ 1 − \frac{λ_{n}}{λ_{1}} .

This result is not far from the ones cited by Haemers [3, p. 22] (where eigenvalues are sorted in decreasing order). But our result provides a lower bound on the number (or sum of weights) of edges that one should remove to get a k-colorable graph.

12.1. Example. For the graph of section 9.3 with 7 vertices and 14 weighted edges, whose sum of weights is 21, we have λ_{1} = λ_{2} = −2.69 and λ_{7} = 6, the bound is \frac{7}{3}(6+2.69) = 20.27 < 21 and this suffices to see that the graph is not 3-colorable.

13. Conclusion

We have proposed some techniques from degree sequences and from spectra, but of course not everything can be obtained from these methods, since there exist pairs of cospectral regular graphs, like the Shrikhande graph and the cartesian sum K_{4} × K_{4}, both regular of degree 6 and spectrum {(−2)^{[9]}, 2^{[6]}, 6}. Besides the presence of K_{4} (only in the second one), or the structure of neighbourhoods of vertices (C_{6} and K_{3}∪K_{3} respectively) they can be distinguished by their chip-firing group: see [1].

References

1. N. Biggs, Algebraic potential theory on graphs, Bull. Lond. Math. Soc. 29 (1997), 641–682.

2. C. Godsil and L. Lovász, Tools from linear algebra, in R. L. Graham, M. Grötschel, and L. Lovász (eds.), Handbook of Combinatorics, chapter 31, Elsevier, 1995, 1705–1748.

3. W. Haemers, Eigenvalue techniques in design and graph theory, Number 121 in Mathematical Centre Tracts, Mathematisch Centrum, Amsterdam, 1980.

4. R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991.

5. D. Karger, R. Motwani, and M. Sudan, in Proceedings of the 35th annual IEEE Symposium on Foundations of Computer Science, FOCS 94 (Santa Fe, New Mexico 1994), IEEE Computer Society Press, 1994, 2–13.

Laboratoire de Recherche en Informatique (Received 23 07 2009) Université Paris-Sud, Orsay, France (Revised 23 07 2010 and 19 02 2011)

    Charles.Delorme@lri.fr