The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements

Elias M. Hagos

                    emhagos@hotmail.com

Submitted: June 10, 1999; Accepted: February 13, 2000.

Abstract

The question of whether the characteristic polynomial of a simple graph is uniquely determined by the characteristic polynomials of its vertex-deleted subgraphs is one of the many unresolved problems in graph reconstruction. In this paper we prove that the characteristic polynomial of a graph is reconstructible from the characteristic polynomials of the vertex-deleted subgraphs of the graph and its complement.

AMS Classification Numbers: 05C60, 05C50

1 Introduction

Let G = (V, E) be a simple graph with a vertex set of at least three elements V = {1, …, n}. We denote by E(G) the set of its edges. A subgraph of G obtained by deleting vertex i and all its incident edges is called a vertex-deleted subgraph of G and is denoted by G_{i}. The collection of vertex-deleted subgraphs of G is known as its deck. The characteristic polynomial of G is the characteristic polynomial of its adjacency matrix A and is defined by P_{G}(x) = det(xI − A). We call the collection of the characteristic polynomials of the vertex-deleted subgraphs the polynomial deck of G and denote it by P(G) = {P_{G_{1}}, P_{G_{2}}, …, P_{G_{n}}}. In general, a property of a graph is said to be reconstructible if it is uniquely determined by its deck. Tutte [11] proved that the characteristic polynomial of a graph is reconstructible from its deck. But is the full knowledge of the vertex-deleted subgraphs necessary to reconstruct the characteristic polynomial? Gutman and Cvetković [6] first raised the still unresolved question of whether the polynomial deck of a simple graph on at least three vertices contains enough information to reconstruct its characteristic polynomial. Some results are reported in [2, 8, 10]. In this paper, we prove that P_{G}(x) is uniquely determined by the collection \{( P_{G_{u}}(x), P_{\overline{G}_{u}}(x) ) | u ∈ V (G)\}.

2 Preliminaries

We begin by listing some known facts and derive lemmas that are used to prove the main theorem. The degree of vertex i is denoted by d_{G,i}. Let W_{G}(x), W_{G,i}(x) and C_{G,i}(x) respectively be the generating functions for the total number of walks, number of walks that originate at vertex i and number of closed walks that start and end at vertex i. Then,

W_{G}(x) = \frac{1}{x} (\frac{(−1)^{n}P_{\overline{G}}(−1 − 1/x)}{P_{G}(1/x)} − 1) , (1)

(2)  W_{G}(x) = W_{G_{i}}(x) + \frac{W_{G,i}^{2}(x)}{C_{G,i}(x)},  i = 1, …, n,
(3)  C_{G,i}(x) = \frac{1}{x} \frac{P_{G_{i}}(1/x)}{P_{G}(1/x)},  i = 1, …, n.

Eqn. (1) is derived in [1], p.45 and (2, 3) in [5].

Lemma 2.1 Let G and H be two graphs of the same order with |E(G)| > |E(H)|. Then there exists an ε > 0 such that x ∈ (0, ε) ⇒ W_{G}(x) > W_{H}(x).

Proof. Let W(x) = ( w_{ij}(x) ) where w_{ij}(x) is the generating function for the number of walks from vertex i to j. Since A_{ij}^{k} is the number of walks of length k from i to j, we have

W(x) = ∑_{k=0}^{∞} x^{k}A^{k}. (4)

This may be written as W(x) = I+xA+x^{2}A^{2} ∑_{k=0}^{∞} x^{k}A^{k}. Let e be the vector all ones. Then W_{G}(x) = e^{t} W(x) e = n + 2 |E(G)| x + o(x^{2}), from which the claim immediately follows. ■

Lemma 2.2 Given a graph G, there exists an ε > 0 such that for any pair i, j of its vertices (d_{G,i} − d_{G,j})(W_{G_{i}}(x) − W_{G_{j}}(x)) ≤ 0 for x ∈ (0, ε).

Proof. The claim is obvious when d_{G,i} = d_{G,j}. If d_{G,i} > d_{G,j} then |E(G_{i})| < |E(G_{j})| and by Lemma 2.1, there is an interval (0, ε_{ij}) such that W_{G_{i}}(x) < W_{G_{j}}(x). If, on the other hand d_{G,i} < d_{G,j}, then |E(G_{i})| > |E(G_{j})| and there is an interval (0, ε_{ij}) over which W_{G_{i}}(x) > W_{G_{j}}(x). Choosing ε = min_{1≤i,j≤n}ε_{ij} proves the lemma. ■

Lemma 2.3

P_{G}(1/x) = \frac{1}{x(xW_{G}(x))′} ∑_{i=1}^{n} (W_{G}(x) − W_{G_{i}}(x)) P_{G_{i}}(1/x).

Proof. From (4) we have W(x) = I + x A W(x) so that W(x) = (I − xA)^{−1}. Let w(x) = W(x) e = (W_{G,1}(x), …, W_{G,n}(x))^{t}. By differentiating e^{t} (I − xA)^{−1} e, we first obtain

W′_{G}(x) = e^{t} (I − xA)^{−2} Ae = w(x)^{t}Aw(x).

Next,

W_{G}(x) = e^{t}W(x)W(x)^{−1}W(x)e = w(x)^{t} (I − xA) w(x)
= w(x)^{t}w(x) − xW′_{G}(x).

Therefore

(xW_{G}(x))′ = w(x)^{t}w(x). (5)

From (2) and (3) we have

P_{G}(1/x) W_{G,i}^{2}(x) = \frac{1}{x}(W_{G}(x) − W_{G_{i}}(x)) P_{G_{i}}(1/x).

Summing this over i and using (5) proves the lemma. ■

Lemma 2.4 Graphs with identical characteristic polynomial decks have identical degree sequences [6].

Proof. Let G, H be graphs such that P_{G_{i}} = P_{H_{i}}, i = 1, …, n. The number of edges of a graph is determined by its characteristic polynomial. Thus, |E(G_{i})| = |E(H_{i})|, i = 1, …, n. Now ∑_{i} |E(G)| − |E(G_{i})| = n|E(G)| − ∑_{i} |E(G_{i})| = 2|E(G). Then, |E(G)| = ∑_{i} |E(G_{i})|/(n − 2) = |E(H)|. Thus, d_{G,i} = d_{H,i}, i = 1, …, n. ■

3 Main theorem

Theorem 3.1 The characteristic polynomial of a graph G is reconstructible from the collection \{( P_{G_{u}}(x), P_{\overline{G}_{u}}(x) ) | u ∈ V (G)\}.

Proof. Let H be any graph such that (P_{H_{i}}(x), P_{\overline{H}_{i}}(x) ) = (P_{G_{i}}(x), P_{\overline{G}_{i}}(x) ), i = 1, …, n. By (1), W_{G_{i}}(x) = W_{H_{i}}(x), i = 1, …, n. This result is used to show that there is an interval (0, ε) over which W_{G}(x) = W_{H}(x). We then conclude by Lemma 2.3 that P_{H}(x) = P_{G}(x).

Consider the interval (0, ε) from Lemma 2.2 and let x be any point in this interval. Suppose W_{G}(x) > W_{H}(x). Then, for any pair of vertices i, j

(d_{G,i} − d_{G,j})(W_{G_{i}}(x) − W_{G_{j}}(x))(W_{G}(x) − W_{H}(x)) ≤ 0. (6)

Because W_{G_{i}}(x) = W_{H_{i}}(x), W_{G_{j}}(x) = W_{H_{j}}(x) and using (3) we have

\begin{matrix}(W_{G_{i}}(x) − W_{G_{j}}(x)) & (W_{G}(x) − W_{H}(x)) \\ = & (W_{G}(x) − W_{G_{i}}(x))(W_{H}(x) − W_{H_{j}}(x)) \\ − (W_{H}(x) − W_{H_{i}}(x))(W_{G}(x) − W_{G_{j}}(x)) \\ = & \frac{W_{G,i}^{2}(x)}{C_{G,i}(x)} \frac{W_{H,j}^{2}(x)}{C_{H,j}(x)} − \frac{W_{H,i}^{2}(x)}{C_{H,i}(x)} \frac{W_{G,j}^{2}(x)}{C_{G,j}(x)}. \end{matrix} (7)

Next we note that

\begin{matrix}C_{G,i}(x) C_{H,j}(x) = & \frac{1}{x} \frac{P_{G_{i}}(1/x)}{P_{G}(1/x)} \frac{1}{x} \frac{P_{H_{j}}(1/x)}{P_{H}(1/x)} \\ = & \frac{1}{x} \frac{P_{H_{i}}(1/x)}{P_{H}(1/x)} \frac{1}{x} \frac{P_{G_{j}}(1/x)}{P_{G}(1/x)} = C_{H,i}(x) C_{G,j}(x). \end{matrix} (8)

By using (8) and (7) in (6) and factoring we get

(d_{G,i} − d_{G,j})(W_{G,i}(x)W_{H,j}(x) − W_{H,i}(x)W_{G,j}(x))

(\frac{W_{G,i}(x)W_{H,j}(x) + W_{H,i}(x)W_{G,j}(x)}{C_{H,i}(x)C_{G,j}(x)}) ≤ 0.

The last term is positive when x > 0. Thus,

(d_{G,i} − d_{G,j})(W_{G,i}(x)W_{H,j}(x) − W_{H,i}(x)W_{G,j}(x)) ≤ 0.

By Lemma 2.4, d_{G,i} = d_{H,i}, d_{G,j} = d_{H,j}. Therefore, we derive

\begin{matrix}d_{G,i} & W_{G,i}(x) W_{H,j}(x) + d_{G,j} W_{G,j}(x) W_{H,i}(x) \\ − & d_{H,i} W_{H,i}(x) W_{G,j}(x) − d_{H,j} W_{H,j}(x) W_{G,i}(x) ≤ 0. \end{matrix} (9)

We sum (9) over all vertices i, j to get,

∑_{i}d_{G,i}W_{G,i}(x) ∑_{j} W_{H,j}(x) + ∑_{j} d_{G,j}W_{G,j}(x) ∑_{i} W_{H,i}(x)
− ∑_{i} d_{H,i}W_{H,i}(x) ∑_{j} W_{G,j}(x) − ∑_{j} d_{H,j}W_{H,j}(x) ∑_{i} W_{G,i}(x) ≤ 0,

and simplify it to

W_{H}(x) ∑_{i} d_{G,i}W_{G,i}(x) − W_{G}(x) ∑_{i} d_{H,i}W_{H,i}(x) ≤ 0. (10)

From (4) we have W(x) = I+x A W(x). Hence, W_{G}(x) = e^{t}W(x)e = n+x ∑_{i=1}^{n} d_{G,i}W_{G,i}(x). Using this result in (10) and because x > 0 we get

W_{H}(x) (W_{G}(x) − n) − W_{G}(x) (W_{H}(x) − n) ≤ 0,

from which we conclude W_{G}(x) ≤ W_{H}(x). This contradicts the assumption that W_{G}(x) > W_{H}(x). Therefore, W_{G}(x) = W_{H}(x). ■

After showing that W_{G}(x) is reconstructible from \{(P_{G_{u}}(x), P_{\overline{G}_{u}}(x)) | u ∈ V (G)\}, we used Lemma 2.3 to prove that the characteristic polynomial is also reconstructible. But there is an alternative argument to do this. Let P′_{G}(x) be the derivative of the characteristic polynomial of G. Then (see [9]) P′_{G}(x) = ∑_{i=1}^{n} P_{G_{i}}(x) so that if P_{G}(x) = ∑_{k=0}^{n} a_{G,k}x^{k}, then a_{G,k} = (∑_{i=1}^{n} a_{G_{i},k−1}) /k, k = 1, …, n. The constant term a_{G,0} is thus the only coefficient possibly not determined by P(G). However, a_{G,0} is reconstructible if in addition to a_{G,k}, k = 1, …, n, a single eigenvalue of G is reconstructible [6].

An eigenvalue λ of a graph is called main if it has an associated eigenvector x such that e^{t}x ≠ 0. Let M(G) denote the set of main eigenvalues of G. Deo, Harary and Schwenk [4] have shown that W_{G}(x) = W_{H}(x) iff M(G) = M(H) and M(\overline{G}) = M(\overline{H}). They call such graphs comain. Thus, by Theorem 3.1 M(G) is reconstructible from \{( P_{G_{u}}(x), P_{\overline{G}_{u}}(x) ) | u ∈ V (G)\} and since a graph has at least one main eigenvalue, so is a_{G,0}.

4 Discussion

The original problem of whether P(G) uniquely determines a_{G,0} is still open. It is part of a general class of reconstruction problems which ask whether a graph invariant I(G) is uniquely determined by the collection I(G_{u}), u ∈ V (G). In [8] Schwenk expresses his suspicion that P_{G}(x) is not reconstructible from P(G) but that counter-examples will be difficult to find.

While searching for a counter-example, I found many pairs of non-cospectral graphs G, H such that P′_{G}(x) = P′_{H}(x). An example of two such graphs is shown in Figure 1 where P_{G}(x) = x^{12} − 13x^{10} + 56x^{8} − 102x^{6} + 80x^{4} − 22x^{2} and P_{H}(x) = P_{G}(x) + 1. The two graphs have identical degree sequence and P_{G_{2}}(x) = P_{H_{2}}(x), P_{G_{3}}(x) = P_{H_{3}}(x). Moreover, the characteristic polynomials of the pairs {G_{7}, H_{7}}, {G_{11}, H_{12}} and {G_{12}, H_{11}} differ only in their respective coefficients of x. The list of the characteristic polynomials of the vertex deleted subgraphs of the two graphs is shown in Table 1. This is hardly an indication that counter-examples exist and it may well turn out that P_{G_{i}}(x) = P_{H_{i}}(x), i = 1, …, n if and only if P_{\overline{G}_{i}}(x) = P_{\overline{H}_{i}}(x), i = 1, …, n.

graph a_{12} a_{11} a_{10} a_{9} a_{8} a_{7} a_{6} a_{5} a_{4} a_{3} a_{2} a_{1} a_{0}
G  1 0 -13 0 56 0 -102 0 80 0 -22 0 0
G_{1}  1 0 -12 0 47 0 -76 0 51 0 -11 0
G_{2}  1 0 -12 0 47 0 -76 0 51 0 -11 0
G_{3}  1 0 -12 0 45 0 -67 0 40 0 -8 0
G_{4} 1 0 -11 0 37 0 -44 0 16 0 0 0
G_{5}  1 0 -11 0 37 0 -47 0 22 0 -2 0
G_{6}  1 0 -11 0 40 0 -57 0 27 0  0 0
G_{7}  1 0 -11 0 35 0 -40 0 14 0  0 0
G_{8}  1 0 -11 0 37 0 -53 0 34 0 -8 0
G_{9} 1 0 -10 0 30 0 -34 0 12 0 0 0
G_{10}  1 0 -10 0 34 0 -46 0 22 0 -2 0
G_{11}  1 0 -10 0 33 0 -43 0 20 0 -2 0
G_{12}  1 0 -9 0 26 0 -29 0 11 0  0 0
H  1 0 -13 0 56 0 -102 0 80 0 -22 0 1
H_{1}  1 0 -12 0 46 0 -69 0 37 0 -2 0
H_{2}  1 0 -12 0 47 0 -76 0 51 0 -11 0
H_{3}  1 0 -12 0 45 0 -67 0 40 0 -8 0
H_{4}  1 0 -11 0 38 0 -49 0 23 0 -3 0
H_{5}  1 0 -11 0 37 0 -46 0 20 0 -2 0
H_{6}  1 0 -11 0 41 0 -63 0 37 0 -4 0
H_{7}  1 0 -11 0 35 0 -40 0 14 0 -1 0
H_{8}  1 0 -11 0 37 0 -53 0 33 0 -7 0
H_{9}  1 0 -10 0 30 0 -35 0 15 0 -2 0
H_{10}  1 0 -10 0 33 0 -42 0 19 0 -2 0
H_{11}  1 0 -9 0 26 0 -29 0 11 0 -1 0
H_{12}  1 0 -10 0 33 0 -43 0 20 0 -1 0

Table 1: Coefficients of the characteristic polynomials of the graphs of Figure 1 and their vertex-deleted subgraphs.

[figure: •; 7; •; 3; •; 8; •; 9; •; 10; •; 5; •; 6; •; 4; •; 11; •; 12; •; 2; •; 1; G; H; •; 7; •; 3; •; 8; •; 9; •; 10; •; 5; •; 6; •; 4; •; 11; •; 12; •; 2; •; 1]

Figure 1: Two non-cospectral graphs with P′_{G}(x) = P′_{H}(x).

Theorem 3.1 suggests that perhaps the correct problem to pose in general is: Is I(G) uniquely determined by the collection \{(I(G_{u}), I( \overline{G}_{u}) ) | u ∈ V (G)\}? The vertexdeleted subgraphs are not essential to reconstruct the elementary invariants of a graph. For example, the number of edges of a graph is determined from that of the subgraphs as |E(G)| = ∑_{i} |E(G_{i})|/(n−2). The degree sequence of G, denoted by D_{G}, is uniquely determined by {D_{G_{i}} | i ∈ V (G)}. The degree sequence of a vertex i, denoted by D_{G,i}, is the list of the degrees of its neigbours in ascending order. It is easy to show that {D_{G,i} | i ∈ V (G)} is reconstructible from {D_{G_{i},j} | i ∈ V (G), j ∈ V (G_{i})}. In each of these cases, we note that the invariants are equal for two graphs iff they are also equal for their complements. We rely on these observations and Theorem 3.1 to suggest the following problem.

Problem. Find examples of non-trivial invariants I(G) of a graph G with at least three vertices which are reconstructible from their collection \{(I(G_{u}), I( \overline{G}_{u}) ) | u ∈ V (G)\}.

The celebrated reconstruction conjecture which asserts that the isomorphism class of a graph on at least three vertices is uniquely determined by the isomorphism classes of its vertex-deleted subgraphs is the most general case of problems of this type. There are counter-examples to the question of whether a graph invariant I(G) is reconstructible from the collection \{(I(G_{u}), I( \overline{G}_{u}) ) | u ∈ V (G)\}. This was pointed out to the author (who originally hazarded it as a conjecture) by Brendan Mckay [7] who observed that Hamiltonicity is not reconstructible in this sense. His observation was: “Let I(G) = ‘G is Hamiltonian’. Choose a large even number n. Let G be a cubic hypohamiltonian graph (which exist for all large even orders). All the vertex-deleted subgraphs of both G and \overline{G} are Hamiltonian (for G, by definition; for \overline{G}, because the degree is high enough to imply it), yet G is not Hamiltonian. For the second graph, take H = \overline{G}. Again all the vertex-deleted subgraphs of both H and \overline{H} are Hamiltonian, yet this time H is also Hamiltonian.”

A different problem than that proved by Theorem 3.1 is the question of whether P_{G}(x) is reconstructible from the two decks P(G), P(\overline{G}). Unlike the condition of Theorem 3.1, here it is not known a priori which characteristic polynomials from the two decks belong to a vertex-deleted subgraph and its complement. This is crucial to the proof of Theorem 3.1.

Finally, the referee noted that the result from the title can be reformulated as follows: The eigenvalues and main angles of a graph can be uniquely reconstructed from the eigenvalues and main angles of its vertex deleted subgraphs. This follows from a formula connecting characteristic polynomials of a graph and its complement and main angles (see, for example, [3] p. 99).

References

[1] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs - Theory and Applications, Academic Press, New York 1980.

[2] D. Cvetković and M. Lepovic, Seeking counterexamples to the reconstruction conjecture for characteristic polynomials of graphs and a positive result, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 116(1998), No. 23, pp.91-100.

[3] D. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of graphs. Encyclopedia of Mathematics and its Applications, 66. Cambridge University Press, Cambridge, 1997.

[4] N. Deo, F. Harary and A.J. Schwenk, An Eigenvector Characterization of Cospectral Graphs Having Cospectral Joins, Ann. N.Y. Acad. Sci. 555(1989), pp.159-166.

[5] C.D. Godsil and B.D. McKay, Spectral Conditions for the Reconstructibility of a Graph, Journal of Combinatorial Theory (B), 30(1981), pp.285-289.

[6] I. Gutman, D.M. Cvetković, The Reconstruction Problem for the Characteristic Polynomial of Graphs, Publ. Elektrotehn, Fak.Ser.Fiz., No 498-541, Univ. Beograd, 1975, pp.45-48.

[7] B.D. McKay, Private communication.

[8] A.J. Schwenk, Spectral Reconstruction Problems, Ann. N.Y. Acad. Sci. 328(1979), pp.183-189.

[9] A.J. Schwenk, On the Eigenvalue of a Graph, Selected Topics in Graph Theory, (L.W. Beineke and R.J. Wilson, eds.), Academic Press, New York, 1979, pp.307-336.

[10] S.K. Simić, A Note on Reconstructing the Characteristic Polynomial of a Graph, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, (J. Nešetřil and M. Fiedler, eds.), Elsevier Science Publishers, B.V., 1992, pp.315-

the electronic journal of combinatorics 7 (2000), #R12 9

[11] W.T. Tutte, All the king’s horses, Graph Theory and Related Topics, (J.A. Bondy and U.S.R. Murty, eds.), Academic Press, New York, 1979, pp.15-33.