Multivariate Matching Polynomials of Cyclically Labelled Graphs

John P. McSorley and Philip Feinsilver, Department of Mathematics, Mailcode 4408, Southern Illinois University, Carbondale. IL 62901-4408. mcsorley60@hotmail.com pfeinsil@math.siu.edu

Keywords

Matching, Matching Polynomial, Labelled, Graph, Recurrence, MacMahon’s Master Theorem

Abstract

We consider the matching polynomials of graphs whose edges have been cyclically labelled with the ordered set of t labels {x_{1}, …, x_{t}}.

We first work with the cyclically labelled path, with first edge label x_{i}, followed by N full cycles of labels {x_{1}, …, x_{t}}, and last edge label x_{j}. Let Φ_{i,Nt+j} denote the matching polynomial of this path. It satisfies the (τ, Δ)-recurrence: Φ_{i,Nt+j} = τ Φ_{i,(N−1)t+j} −Δ Φ_{i,(N−2)t+j}, where τ is the sum of all non-consecutive cyclic monomials in the variables {x_{1}, …, x_{t}} and Δ = (−1)^{t} x_{1} ⋯ x_{t}. A combinatorial/algebraic proof and a matrix proof of this fact are given. Let G_{N} denote the first fundamental solution to the (τ, Δ)-recurrence. We express G_{N} (i) as a cyclic binomial using the Symmetric Representation of a matrix, (ii) in terms of Chebyshev polynomials of the second kind in the variables τ and Δ, and (iii) as a quotient of two matching polynomials. We extend our results from paths to cycles and rooted trees.

Introduction

The matching polynomial of a graph is defined in Farrell [1]. Often in pure mathematics and combinatorics it is interesting to consider cyclic structures, eg., cyclic groups, cyclic designs, and circulant graphs. Here we consider the (multivariate) matching polynomial of a graph whose edges have been cyclically labelled.

We concentrate mainly on paths, cycles and trees. To cyclically label a path with the ordered set of t labels {x_{1}, …, x_{t}}, label the first edge with any x_{i}, the second with x_{i+1}, and so on until label x_{t} has been used, then start with x_{1}, then x_{2}, …, x_{t}, then x_{1} again …, repeating cyclically until all edges have been labelled, with the last edge receiving label x_{j}. Suppose that N full cycles of labels {x_{1}, …, x_{t}} have been used. Call the matching polynomial of this labelled path Φ_{i,Nt+j}. We show, for a fixed i and j, that Φ_{i,Nt+j} satisfies the following recurrence, the (τ, Δ)-recurrence:

Φ_{i,Nt+j} = τ Φ_{i,(N−1)t+j} − Δ Φ_{i,(N−2)t+j},

where τ is the sum of all non-consecutive cyclic monomials in the variables {x_{1}, …, x_{t}} (see Section 1), and Δ = (−1)^{t} x_{1} ⋯ x_{t}. We give two different proofs of this fact. The first one is a combinatorial/algebraic proof in Section 2 that uses the following Theorem concerning decomposing the matching polynomial M(G, x) of a graph. Theorem Let G be a labelled graph, H a subgraph of G, and M_{H} a matching of H, then

M(G, x) = ∑_{M_{H}} M_{H}(x) M(G − H − \overline{M}_{H}, x),

where the summation is over every matching M_{H} of H. The second proof (Section 3) uses a matrix formulation of the recurrences that we develop.

Let G_{N} denote the first fundamental solution to the (τ, Δ)-recurrence; three different expressions for G_{N} are given in Section 4. The first expression is a sum of cyclic binomials and uses the Symmetric Representation of matrices from Section 3; the second involves Chebyshev polynomials of the second kind in the variables τ and Δ; and the third is a quotient of two matching polynomials, see Theorem 4.5.

In Section 5 we extend our results from paths to cycles and rooted trees; we find explicit forms for the matching polynomial of a cyclically labelled cycle, and indicate how to find the matching polynomial of a cyclically labelled rooted tree, again using the decomposition Theorem stated above.

Many examples are given throughout the paper.

1 The multivariate matching polynomial of a graph, its decomposition; non-consecutive and non-consecutive cyclic functions

For a fixed t ≥ 1 we use multi-index notations: k = (k_{1}, …, k_{t}), where each k_{s} ≥ 0, 0 = (0, …, 0), and variables x = (x_{1}, …, x_{t}). The total degree of k is denoted by |k| = k_{1} + ⋯ + k_{t}.

Let G be a finite simple graph with vertex set V (G) where |V (G)| ≥ 1, and edge set E(G). We label these edges from the t commutative variables {x_{1}, …, x_{t}}, exactly one label per edge. A matching of G is a collection of edges, no two of which have a vertex in common. A k-matching of G is a matching with exactly k_{s} edges with label x_{s}, for each s with 1 ≤ s ≤ t. If M_{G} is a k-matching of G we define its weight to be

M_{G}(x) = x_{1}^{k_{1}} ⋯ x_{t}^{k_{t}}.

The empty matching of G, which contains no edges, is denoted by M_{∅}; it is the unique 0-matching and its weight is M_{∅}(x) = 1.

Define the multivariate matching polynomial, or simply, the matching polynomial, of G, by

M(G, x) = ∑_{M_{G}} M_{G}(x),

where the summation is over every matching M_{G} of G.

Denote the number of k-matchings of G by a(G, k). Then an alternative definition of the multivariate matching polynomial of G is

M(G, x) = ∑_{(k_{1},...,k_{t})} a(G, k) x_{1}^{k_{1}} ⋯ x_{t}^{k_{t}}.

The multivariate matching polynomial is a natural extension of the matching polynomial of Farrell [1]. Indeed, here with t = 1 and in [1] with w_{1} = 1 and w_{2} = x_{1}, the polynomials are identical.

Let P_{1} be the graph with one vertex and no edges, i.e., an isolated vertex; we define M(P_{1}, x) = 1. Now suppose G′ = G ∪ nP_{1}, where n ≥ 1, i.e., G′ is the disjoint union of G and n isolated vertices, then we define M(G′, x) = M(G, x).

For any edge e ∈ E(G), let \overline{e} denote the set of edges that are incident to e; and for any subgraph H of G, let \overline{H} = ∪_{e∈E(H)}\overline{e}. Define \overline{M}_{∅} = ∅. Also let G − H be the graph obtained from G when all the edges of H are removed, so G − H has the same vertex set as G.

Now let H be a fixed subgraph of G and let M_{H} be a matching of H. In the following theorem we express M(G, x) as a sum of terms, each term containing the weight of a fixed matching, M_{H}(x), of H; we call this decomposing M(G, x) at H.

Theorem 1.1 Let G be a graph labelled as above, H a fixed subgraph of G, and M_{H} a matching of H. Then

M(G, x) = ∑_{M_{H}} M_{H}(x) M(G − H − \overline{M}_{H}, x),  (1)

where the summation is over every matching M_{H} of H.

Proof. Let M_{G} be a matching of G which induces a (fixed) matching M_{H} on H, i.e., M_{G} contains exactly M_{H} and no other edges from H. Then M_{G}(x) = M_{H}(x) M(x) where M is a matching of G with no edges in H, and also with no edges in \overline{M}_{H} or else M_{G} would not be a matching. Hence, M is a matching of G − H − \overline{M}_{H}, i.e., M(x) is a term of M(G − H − \overline{M}_{H}, x). So M_{H}(x) M(G − H − \overline{M}_{H}, x) is the sum of the weights of all the matchings in G which induce M_{H} on H.

Now every matching in G induces some matching on H, so we may sum over all matchings in H to give (1).

Theorem 1.1 extends known facts about matching polynomials, eg., see Theorem 1 of Farrell [1] for the case where H is a single edge. We have the corresponding:

Corollary 1.2 Let G be a graph labelled as above, and let H = e labelled with x be an edge of G. Then

M(G, x) = M(G − e, x) + x M(G − e − \overline{e}, x).  (2)

Proof. The result comes from (1) since H = e has just two matchings: the empty matching M_{∅} with weight M_{∅}(x) = 1, and the matching e with weight M_{e}(x) = x.

Notation Throughout this paper we use P_{m} to denote the path with m vertices and m − 1 edges.

Fix i and j where 1 ≤ i ≤ j ≤ t. Consider the path P_{j−i+2} with its j−i+1 edges labelled from the ordered set {x_{i}, …, x_{j}}, the first edge receiving label x_{i}, and the last x_{j}; see Fig. 1.

•  •  •  •  •  • x_{i}  x_{i+1}  x_{i+2}  x_{j} Fig. 1: The labelled path P_{j−i+2} with matching polynomial ϕ_{i,j}.

The pair x_{s}x_{s+1} for any fixed s with i ≤ s ≤ j − 1 is called a consecutive pair. A monomial from the ordered set {x_{i}, …, x_{j}} that contains no consecutive pairs is a non-consecutive monomial, a nc -monomial. Note that the empty monomial is a nc -monomial that we denote by 1.

Let ϕ_{i,j} be the sum of all nc -monomials in the ordered variables {x_{i}, …, x_{j}}. Then ϕ_{i,j} = M(P_{j−i+2}, x) is the matching polynomial of the labelled path P_{j−i+2}. We call the functions ϕ_{i,j} elementary non-consecutive functions, and for any i ≥ 1 define the initial values

ϕ_{i,i−2} = ϕ_{i,i−1} = 1.  (3)

These initial values ensure that the following recurrence is valid for any j with i ≤ j ≤ t.

Theorem 1.3 For a fixed i and j with 1 ≤ i ≤ j ≤ t and the initial values in (3), we have

ϕ_{i,j} = ϕ_{i,j−1} + x_{j} ϕ_{i,j−2}.  (4)

Proof. Let e be the rightmost edge of G = P_{j−i+2} shown in Fig. 1, and apply (2).

Example 1 For arbitrary i we have ϕ_{i,i} = 1 + x_{i}, ϕ_{i,i+1} = 1 + x_{i} + x_{i+1},

ϕ_{i,i+2} = 1 + x_{i} + x_{i+1} + x_{i+2} + x_{i}x_{i+2},
ϕ_{i,i+3} = 1 + x_{i} + x_{i+1} + x_{i+2} + x_{i+3} + x_{i}x_{i+2} + x_{i}x_{i+3} + x_{i+1}x_{i+3}.

Example 2 For arbitrary i, putting j = i − 1 and j = i − 2 in Recurrence (4) and using (3) give

ϕ_{i,i−3} = 0 and ϕ_{i,i−4} = \frac{1}{x_{i−2}} .

In the second equation, if i = 1 we replace x_{−1} by x_{t−1}, and if i = 2 we replace x_{0} by x_{t}.

Consider Recurrence (4). It is convenient to work with a basis of solutions to this recurrence. Denote the first fundamental solution by f_{i,j} and the second by g_{i,j}, with initial values

f_{i,i−2} = 0, f_{i,i−1} = 1 and g_{i,i−2} = 1, g_{i,i−1} = 0.  (5)

So

ϕ_{i,i−2} = f_{i,i−2} + g_{i,i−2} and ϕ_{i,i−1} = f_{i,i−1} + g_{i,i−1}.

Now, from Recurrence (4) and strong induction on j, we have (6) below for all j with i ≤ j ≤ t

ϕ_{i,j} = f_{i,j} + g_{i,j}.  (6)
ϕ_{i,j} = ϕ_{i+1,j} + x_{i} ϕ_{i+2,j}.  (7)

Equation (7) comes from decomposing ϕ_{i,j} at the leftmost edge of P_{j−i+2}, whose label is x_{i}, i.e., decomposing ϕ_{i,j} at x_{i}; see Corollary 1.2. These two equations suggest that the fundamental solutions are given by

f_{i,j} = ϕ_{i+1,j} and g_{i,j} = x_{i} ϕ_{i+2,j}.

This is indeed the case:

Lemma 1.4 For any j with i ≤ j ≤ t we have (i) f_{i,j} = ϕ_{i+1,j}, (ii) g_{i,j} = x_{i} ϕ_{i+2,j}.

Proof. We need only prove (i) because of (6) and (7) above.

From (5) we have f_{i,i−2} = 0 and from Example 2 we have ϕ_{i+1,i−2} = 0; thus f_{i,i−2} = ϕ_{i+1,i−2}. Similarly, from (5) and (3), we have f_{i,i−1} = ϕ_{i+1,i−1}. So both f_{i,j} and ϕ_{i+1,j} have the same initial values at j = i−2 and j = i−1 and they both satisfy Recurrence (4), so they are equal for any j with i ≤ j ≤ t.

Thus we know combinatorially what the two fundamental solutions to Recurrence (4) are. The first, f_{i,j}, is the matching polynomial of the path shown in Fig. 2(a); the second, g_{i,j}, is x_{i} × the matching polynomial of the path in Fig. 2(b).

(a)  •  •  •  •  • x_{i+1}  x_{i+2}  x_{j} (b)  •  •  •  • x_{i+2}  x_{j} Fig. 2 (a) The labelled path with matching polynomial f_{i,j}. (b) The labelled path with matching polynomial \frac{g_{i,j}}{x_{i}}.

Example 3 For arbitrary i we have

\begin{matrix}f_{i,i} = 1, & g_{i,i} = x_{i}, \\ f_{i,i+1} = 1 + x_{i+1}, & g_{i,i+1} = x_{i}, \\ f_{i,i+2} = 1 + x_{i+1} + x_{i+2}, & g_{i,i+2} = x_{i} + x_{i}x_{i+2}. \end{matrix}

Now arrange the variables {x_{i}, …, x_{j}} clockwise around a circle. Thus x_{i} and x_{j} are consecutive. Call a pair x_{s}x_{s′} consecutive cyclic if x_{s} and x_{s′} are consecutive on this circle. Call a monomial from {x_{i}, …, x_{j}} a nonconsecutive cyclic monomial — ncc -monomial — if it contains no consecutive cyclic pairs. The empty monomial is a ncc -monomial that we denote by 1.

Let τ_{i,j} be the sum of all ncc -monomials in the variables {x_{i}, …, x_{j}}. Then, for j ≥ i + 2, τ_{i,j} = M(C_{j−i+1}, x) is the matching polynomial of the labelled cycle C_{j−i+1} with j − i + 1 edges and j − i + 1 vertices, shown in Fig. 3; the cycle starts at the large vertex, and proceeds clockwise.

x_{i+1} x_{i} x_{j} Fig. 3: The labelled cycle C_{j−i+1} with matching polynomial τ_{i,j}.

For initial values let

τ_{i,i−1} = 2, τ_{i,i} = 1, and τ_{i,i+1} = 1 + x_{i} + x_{i+1}.  (8)

Lemma 1.5 For any j with i ≤ j ≤ t we have (i) τ_{i,j} = f_{i,j} + g_{i,j−1}, (ii) ϕ_{i,j} − τ_{i,j} = x_{i}x_{j} ϕ_{i+2,j−2}.

Proof. (i) We check this equality at j = i and j = i + 1 using (5), Example 3, and (8). For j ≥ i + 2 we decompose τ_{i,j} at x_{i} yielding τ_{i,j} = ϕ_{i+1,j} + x_{i} ϕ_{i+2,j−1}, which gives (i) via Lemma 1.4. (ii) We check at j = i and j = i + 1 using Examples 1 and 2, and (8). For j ≥ i + 2 the difference ϕ_{i,j} − τ_{i,j} consists of all nc -monomials that contain the consecutive cyclic pair x_{i}x_{j}; clearly this is x_{i}x_{j} × the sum of all nc - monomials on {x_{i+2}, …, x_{j−2}}, i.e., x_{i}x_{j} ϕ_{i+2,j−2}.

Example 4 For arbitrary i we have

\begin{matrix}τ_{i,i+2} = 1 + x_{i} + x_{i+1} + x_{i+2}, \\ τ_{i,i+3} = 1 + x_{i} + x_{i+1} + x_{i+2} + x_{i+3} + x_{i}x_{i+2} + x_{i+1}x_{i+3}. \end{matrix}

2 Cyclically labelled paths; Φ_{i,Nt+j} and the (τ, Δ)-recurrence

Consider a path P and the ordered set of t labels {x_{1}, …, x_{t}}. For a fixed i, where 1 ≤ i ≤ t, and moving from left to right, label the first edge of P with x_{i}, the second with x_{i+1}, and so on until label x_{t} has been used; so the (t−i+1)-th edge receives label x_{t}. Then label edge t−i+2 with x_{1}, and edge t − i + 3 with x_{2}, and so on …, labelling cyclically with {x_{1}, …, x_{t}} until all edges have been labelled. Let the last edge receive label x_{j}, where 1 ≤ j ≤ t. Suppose that N ≥ 0 full cycles of labels {x_{1}, …, x_{t}} have been used beginning at edge t − i + 2. Then if j = t we call this path P (i, Nt), or if 1 ≤ j < t we call it P (i, Nt+j). This labelling is a cyclic labelling. The cyclically labelled path P (i, Nt + j) is shown in Fig. 4. Let Φ_{i,Nt+j}(x) = Φ_{i,Nt+j} denote the matching polynomial of the path P (i, Nt + j).

•  •  •  •  •  •  •  •  •  •  • x_{i} x_{i+1}  x_{t}  x_{1}  x_{t}  x_{1}  x_{j} ∗ } Nt edges Fig. 4: The cyclically labelled path P (i, Nt + j) with matching polynomial Φ_{i,Nt+j}.

We define the initial conditions for Φ_{i,Nt+j} as

N = −1 : Φ_{i,−t+j} = ϕ_{i,j}, for all j with 0 ≤ j ≤ t,  (9)
also N = 0 : Φ_{i,0t+j} = Φ_{i,j}.

In order to find ϕ_{i,j} if j < i we use the initial values for ϕ_{i,j} from (3) and push back Recurrence (4), as shown in Example 2.

Now Φ_{i,Nt+j} satisfies the same recurrence as that of ϕ_{i,j}, Recurrence (4); the proof is similar, noting that x_{0} must be replaced by x_{t}, and considering Nt − 1 as (N − 1)t + t − 1, etc.

Lemma 2.1 For any N ≥ −1 and j with 0 ≤ j ≤ t we have

Φ_{i,Nt+j} = Φ_{i,Nt+j−1} + x_{j} Φ_{i,Nt+j−2}.  (10)

Notation For i = 1 we write ϕ_{i,j} = ϕ_{1,j} = ϕ_{j} and ϕ_{t} = ϕ, also τ_{1,j} = τ_{j} and τ_{t} = τ, and f_{1,j} = f_{j}, etc. Also let Δ = (−1)^{t} x_{1} ⋯ x_{t}.

Lemma 2.2 For any N ≥ 0 and any j with 0 ≤ j ≤ t we have

Φ_{i,Nt+j} = Φ_{i,Nt} f_{j} + Φ_{i,Nt−1} g_{j}.  (11)

Proof. With N = 0 and j = 0 Equation (11) is true using the initial values f_{0} = 1 and g_{0} = 0 of (5) with i = 1. Otherwise, consider the path P (i, Nt + j) of Fig. 4 and decompose its matching polynomial, Φ_{i,Nt+j}, at the edge labelled x_{1} marked with a ∗. This gives

Φ_{i,Nt+j} = Φ_{i,Nt} ϕ_{2,j} + x_{1} Φ_{i,Nt−1} ϕ_{3,j}
= Φ_{i,Nt} f_{j} + Φ_{i,Nt−1} g_{j},

using Lemma 1.4.

Now we define the second order (τ, Δ)−recurrence

Θ_{N} = τ Θ_{N−1} − Δ Θ_{N−2}.  (12)

Let G_{N}(x) = G_{N} denote the first fundamental solution to this recurrence. We will evaluate G_{N} in Section 4.

In Theorem 2.4 below we show that, for a fixed i and j, Φ_{i,Nt+j} satisfies the (τ, Δ)-recurrence. First:

Lemma 2.3 For any N ≥ 1 we have

(i) Φ_{i,Nt−1} f_{t} − Φ_{i,Nt} f_{t−1} = Δ Φ_{i,(N−1)t−1},  (13)
(ii) Φ_{i,Nt−1} g_{t} − Φ_{i,Nt} g_{t−1} = −Δ Φ_{i,(N−1)t}.

Proof. (i) Using Recurrence (4) on f_{t} and on Φ_{i,Nt} (see Lemma 2.1), the left-hand side of (13) becomes

Φ_{i,Nt−1} {f_{t−1}+x_{t} f_{t−2}}−{Φ_{i,Nt−1}+x_{t} Φ_{i,Nt−2}} f_{t−1} = −x_{t} {Φ_{i,Nt−2} f_{t−1} − Φ_{i,Nt−1} f_{t−2}}.

The second factor in the right-hand side of this equation is the left-hand side of (13) with subscripts shifted down by 1. After t such iterations the left-hand side of (13) becomes

(−x_{t}) (−x_{t−1}) … (−x_{1}){Φ_{i,(N−1)t−1} f_{0} − Φ_{i,(N−1)t} f_{−1}} = Δ Φ_{i,(N−1)t−1}, using the initial values f_{0} = 1 and f_{−1} = 0. The proof of (ii) is similar.

Now a main result: Φ_{i,Nt+j} satisfies the (τ, Δ)-recurrence.

Theorem 2.4 For any N ≥ 1, and any fixed i with 1 ≤ i ≤ t, and any fixed j with 0 ≤ j ≤ t, we have

Φ_{i,Nt+j} = τ Φ_{i,(N−1)t+j} − Δ Φ_{i,(N−2)t+j}.  (14)

Proof. Due to Recurrences (4) and (10) we need only show that (14) is true when j = t and t − 1. It will then be true for all j with 0 ≤ j ≤ t by pushing back Recurrence (10).

With N ≥ 1 and j = t, Equation (11) gives

Φ_{i,Nt+t} = Φ_{i,Nt} f_{t} + Φ_{i,Nt−1} g_{t}
= Φ_{i,Nt} f_{t} + Φ_{i,Nt−1} g_{t} + Φ_{i,Nt} g_{t−1} − Φ_{i,Nt} g_{t−1}
= Φ_{i,Nt} f_{t} + Φ_{i,Nt} g_{t−1} + Φ_{i,Nt−1} g_{t} − Φ_{i,Nt} g_{t−1}
= τ Φ_{i,Nt} − Δ Φ_{i,(N−1)t},
= τ Φ_{i,(N−1)t+t} − Δ Φ_{i,(N−2)t+t},

using τ = τ_{t} = f_{t} + g_{t−1} from Lemma 1.5(i), and Lemma 2.3(ii) at the fourth line. For j = t − 1 the proof is similar using Lemma 2.3(i).

3 Matrix formulation of recurrences

Here we use matrices to give another proof that Φ_{i,Nt+j} satisfies the (τ, Δ)- recurrence, and prepare for the evaluation of G_{N} in Section 4.

Recall from Section 1 that f_{i,j} and g_{i,j} are the 2 fundamental solutions to Recurrence (4). Now define the matrix

X_{i,j} = (\begin{matrix}g_{i,j−1} & f_{i,j−1} \\ g_{i,j} & f_{i,j} \end{matrix}) .

Then the recurrences for f_{i,j} and g_{i,j} can be written as:

X_{i,j} = (\begin{matrix}0 & 1 \\ x_{j} & 1 \end{matrix}) (\begin{matrix}g_{i,j−2} & f_{i,j−2} \\ g_{i,j−1} & f_{i,j−1} \end{matrix}) = (\begin{matrix}0 & 1 \\ x_{j} & 1 \end{matrix}) X_{i,j−1}.  (15)

Consistent with (5) we have X_{i,i−1} = (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) = I, the 2 × 2 identity matrix.

Thus, for j ≥ i, we have

X_{i,j} = (\begin{matrix}0 & 1 \\ x_{j} & 1 \end{matrix}) (\begin{matrix}0 & 1 \\ x_{j−1} & 1 \end{matrix}) ⋯ (\begin{matrix}0 & 1 \\ x_{i} & 1 \end{matrix}) .  (16)

Let 1 = (\begin{matrix}1 \\ 1 \end{matrix}) and e = (\begin{matrix}0 \\ 1 \end{matrix}), and let ⟨· , ·⟩ denote the usual inner product.

Then for j ≥ i, and using (6),

ϕ_{i,j} = ⟨X_{i,j}1, e⟩.  (17)

As before if i = 1 we let X_{1,j} = X_{j} and if j = t we let X = X_{t}, in particular,

X = (\begin{matrix}g_{t−1} & f_{t−1} \\ g_{t} & f_{t} \end{matrix}) = (\begin{matrix}0 & 1 \\ x_{t} & 1 \end{matrix}) (\begin{matrix}0 & 1 \\ x_{t−1} & 1 \end{matrix}) ⋯ (\begin{matrix}0 & 1 \\ x_{1} & 1 \end{matrix}) .  (18)

For N ≥ 0, from (10) we may also write

(\begin{matrix}Φ_{i,Nt+j−1} \\ Φ_{i,Nt+j} \end{matrix}) = (\begin{matrix}0 & 1 \\ x_{j} & 1 \end{matrix}) (\begin{matrix}Φ_{i,Nt+j−2} \\ Φ_{i,Nt+j−1} \end{matrix}) ,

and then repeated use of (15) gives

Φ_{i,Nt+j} = ⟨X_{j}X^{N}X_{i,t}1, e⟩.  (19)

Now using (16) and (18) we see that X_{j}X^{−1}X_{i,t} = X_{i,j}. So, using (17) and (9), we have

⟨X_{j}X^{−1}X_{i,t}1, e⟩ = ⟨X_{i,j}1, e⟩ = ϕ_{i,j} = Φ_{i,−t+j},

thus (19) is true for N = −1 also.

Theorem 3.1 For N ≥ −1 we have

Φ_{i,Nt+j} = ⟨X_{j}X^{N}X_{i,t}1, e⟩.

From Lemma 1.5(i) and (16) we have the following forms for the trace and determinant of matrix X_{i,j}

tr(X_{i,j}) = τ_{i,j} and det(X_{i,j}) = (−1)^{j−i+1}x_{i} ⋯ x_{j}.

In particular, for matrix X from (18), we have

tr(X) = τ  and det(X) = Δ.  (20)

Now let Z be any invertible 2×2 matrix with trace tr(Z) and determinant det(Z), and let T denote transpose. Then the Cayley-Hamilton theorem says that Z^{2} = tr(Z) Z −det(Z) I, so Z^{N} = tr(Z) Z^{N−1}−det(Z) Z^{N−2}, for N ≥ 1. Let u and v ∈ R^{2} and, for N ≥ −1, define Ψ_{N} = ⟨Z^{N}u, v⟩. Then

Lemma 3.2 For N ≥ 1, Ψ_{N} satisfies the recurrence

Ψ_{N} = tr(Z) Ψ_{N−1} − det(Z) Ψ_{N−2},

with initial conditions Ψ_{−1} = ⟨Z^{−1}u, v⟩ and Ψ_{0} = ⟨Z^{0}u, v⟩ = ⟨u, v⟩.

Now for N ≥ −1,

Φ_{i,Nt+j} = ⟨X_{j}X^{N}X_{i,t}1, e⟩ = ⟨X^{N}X_{i,t}1, X_{j}^{T}e⟩.

So, for N ≥ 1, Lemma 3.2 with Z = X, u = X_{i,t}1, and v = X_{j}^{T}e, and (20), gives,

Φ_{i,Nt+j} = τ Φ_{i,(N−1)t+j} − Δ Φ_{i,(N−2)t+j}.

This is a second proof that Φ_{i,Nt+j} satisfies the (τ, Δ)-recurrence.

4 The Symmetric Representation, MacMahon’s Master Theorem, three expressions for G_{N}

Consider polynomials in the variables u_{1}, …, u_{d}. We will work with the vector space whose basis elements are the homogeneous polynomials of degree N in these variables, i.e., with

{u_{1}^{n_{1}} ⋯ u_{d}^{n_{d}} | n_{1} + ⋯ + n_{d} = N, each n_{ℓ} ≥ 0},

this vector space has dimension \binom{N+d−1}{N}.

The symmetric representation of a d × d matrix A = (a_{ℓℓ′}) is the action on polynomials induced by:

u_{1}^{n_{1}} ⋯ u_{d}^{n_{d}} → v_{1}^{n_{1}} ⋯ v_{d}^{n_{d}},

where

v_{ℓ} = ∑_{ℓ′} a_{ℓℓ′}u_{ℓ′}

or, more compactly, v = Au. That is, define the matrix element \left⟨{m_{1}, …, m_{d} \atop n_{1}, …, n_{d}}\right⟩_{A}

to be the coefficient of u_{1}^{n_{1}} ⋯ u_{d}^{n_{d}} in v_{1}^{m_{1}} ⋯ v_{d}^{m_{d}}. Then, for a fixed (m_{1}, …, m_{d}), we have

v_{1}^{m_{1}} ⋯ v_{d}^{m_{d}} = ∑_{(n_{1},...,n_{d})} \left⟨{m_{1}, …, m_{d} \atop n_{1}, …, n_{d}}\right⟩_{A} u_{1}^{n_{1}} ⋯ u_{d}^{n_{d}}.  (21)

Observe that the total degree N = |n| = ∑ n_{ℓ} = |m| = ∑ m_{ℓ}, i.e., homogeneity of degree N is preserved. We use multi-indices: m = (m_{1}, …, m_{d}) and n = (n_{1}, …, n_{d}). Then, for a fixed m, (21) becomes

v^{m} = ∑_{n} \left⟨{m \atop n}\right⟩_{A} u^{n}.

Successive application of B then A shows that this is a homomorphism of the multiplicative semi-group of square d × d matrices into the multiplicative semi-group of square \binom{N+d−1}{N} × \binom{N+d−1}{N} matrices.

Proposition 4.1 Matrix elements satisfy the homomorphism property

\left⟨{m \atop n}\right⟩_{AB} = ∑_{k} \left⟨{m \atop k}\right⟩_{A} \left⟨{k \atop n}\right⟩_{B} .

Proof. Let v = (AB)u and w = Bu. Then,

v^{m} = ∑_{n} \left⟨{m \atop n}\right⟩_{AB} u^{n}
= ∑_{k} \left⟨{m \atop k}\right⟩_{A} w^{k}

= ∑_{n} ∑_{k} \left⟨{m \atop k}\right⟩_{A} \left⟨{k \atop n}\right⟩_{B} u^{n}.

Definition Fix the degree N = ∑ n_{ℓ} = ∑ m_{ℓ}. Define tr_{Sym}^{N}(A), the sym-

metric trace of A in degree N, as the sum of the diagonal elements \left⟨{m \atop n}\right⟩_{A}, i.e.,

tr_{Sym}^{N}(A) = ∑_{m} \left⟨{m \atop m}\right⟩_{A} .

Equality such as tr_{Sym}(A) = tr_{Sym}(B) means that the symmetric traces are equal in every degree N ≥ 0. Remark The action defined here on polynomials is equivalent to the action on symmetric tensor powers, see Fulton and Harris [2], pp. 472-5.

Now it is straightforward to see directly (cf. the diagonal case shown in the Corollary below) that if A is upper-triangular, with eigenvalues λ_{1}, …, λ_{d}, then tr_{Sym}^{N}(A) = h_{N}(λ_{1}, …, λ_{d}), the N^{th} homogeneous symmetric function. The homomorphism property, Proposition 4.1, shows that tr_{Sym}^{N}(AB) = tr_{Sym}^{N}(BA), and that similar matrices have the same trace. Again by the homomorphism property, if two d × d matrices are similar, A = MBM^{−1}, then that relation extends to their respective symmetric representations in every degree. Recall that any matrix is similar to an upper-triangular one with the same eigenvalues. Thus,

Theorem 4.2 Symmetric Trace Theorem (see pp. 51-2 of Springer [5]). We have

\frac{1}{det(I − cA)} = ∑_{N=0}^{∞} c^{N}tr_{Sym}^{N}(A).

Proof. With λ_{ℓ} denoting the eigenvalues of A,

\frac{1}{det(I − cA)} = ∏_{ℓ} \frac{1}{1 − cλ_{ℓ}}

= ∑_{N=0}^{∞} c^{N}h_{N}(λ_{1}, …, λ_{d})
= ∑_{N=0}^{∞} c^{N}tr_{Sym}^{N}(A).

As a Corollary we have MacMahon’s Master Theorem, which we express in the above terminology.

Corollary 4.3 MacMahon’s Master Theorem. The diagonal matrix element \left⟨{m \atop m}\right⟩_{A} is the coefficient of u^{m} = u_{1}^{m_{1}} ⋯ u_{d}^{m_{d}} in

the expansion of det(I − UA)^{−1} where U = diag(u_{1}, …, u_{d}) is the diagonal matrix with entries u_{1}, …, u_{d} on the diagonal.

Proof. From Theorem 4.2, with c = 1, we want to calculate the symmetric trace of UA. By the homomorphism property,

tr_{Sym}^{N}(UA) = ∑_{m} \left⟨{m \atop m}\right⟩_{UA}

= ∑_{m} ∑_{k} \left⟨{m \atop k}\right⟩_{U} \left⟨{k \atop m}\right⟩_{A} .

Now, with v = Uw and v_{ℓ} = u_{ℓ}w_{ℓ}, then

v^{m} = (u_{1}w_{1})^{m_{1}} ⋯ (u_{d}w_{d})^{m_{d}} = u^{m}w^{m} = ∑_{k} \left⟨{m \atop k}\right⟩_{U} w^{k},

i.e.,

\left⟨{m \atop k}\right⟩_{U} = u_{1}^{m_{1}} ⋯ u_{d}^{m_{d}}δ_{k_{1}m_{1}} ⋯ δ_{k_{d}m_{d}}

so that

tr_{Sym}^{N}(UA) = ∑_{m} \left⟨{m \atop m}\right⟩_{A} u^{m}.

Now we restrict ourselves to d = 2, and return to the (τ, Δ)-recurrence. Recall, from (18), the 2 × 2 matrix

X = (\begin{matrix}0 & 1 \\ x_{t} & 1 \end{matrix}) (\begin{matrix}0 & 1 \\ x_{t−1} & 1 \end{matrix}) ⋯ (\begin{matrix}0 & 1 \\ x_{1} & 1 \end{matrix})
= ξ_{t}ξ_{t−1} ⋯ ξ_{1},

where ξ_{s} = (\begin{matrix}0 & 1 \\ x_{s} & 1 \end{matrix}) for 1 ≤ s ≤ t. Let us modify ξ_{s} slightly by defining α_{s} = (\begin{matrix}0 & 1 \\ x_{s} & a_{s} \end{matrix}) for 1 ≤ s ≤ t, and calling

\overline{X} = (\begin{matrix}0 & 1 \\ x_{t} & a_{t} \end{matrix}) (\begin{matrix}0 & 1 \\ x_{t−1} & a_{t−1} \end{matrix}) ⋯ (\begin{matrix}0 & 1 \\ x_{1} & a_{1} \end{matrix})
= α_{t}α_{t−1} ⋯ α_{1}.

Let

tr(\overline{X}) = \overline{τ} and det(\overline{X}) = \overline{Δ},

and let \overline{G}_{N} be the first fundamental solution to the (\overline{τ}, \overline{Δ})-recurrence:

Θ_{N} = \overline{τ} Θ_{N−1} − \overline{Δ} Θ_{N−2}.  (22)

Then

∑_{N=0}^{∞} c^{N} \overline{G}_{N} = \frac{1}{1 − \overline{τ}c + \overline{Δ}c^{2}}
= \frac{1}{det(I − c\overline{X})}
= ∑_{N=0}^{∞} c^{N}tr_{Sym}^{N}(\overline{X}).

So

\overline{G}_{N} = tr_{Sym}^{N}(\overline{X}) = ∑_{m} \left⟨{m \atop m}\right⟩\overline{X} = ∑_{m} \left⟨{m \atop m}\right⟩_{α_{t}α_{t−1}···α_{1}} .

We need to calculate the symmetric trace of \overline{X} and so identify \overline{G}_{N}. By the homomorphism property, we need only find the matrix elements for each matrix α_{s}, multiply together and take the trace.

For α_{s} = (\begin{matrix}0 & 1 \\ x_{s} & a_{s} \end{matrix}) the mapping induced on polynomials is

v_{1} = u_{2} , v_{2} = x_{s} u_{1} + a_{s} u_{2}.  (23)

For any integer N ≥ 0, the expansion of v_{1}^{m}v_{2}^{N−m} in powers of u_{1} and u_{2} is of the form

v_{1}^{m}v_{2}^{N−m} = ∑_{n} \left⟨{m \atop n}\right⟩_{α_{s}} u_{1}^{n}u_{2}^{N−n},  (24)

with the notation for the matrix elements abbreviated accordingly. From (23) and (24), the binomial theorem yields

\left⟨{m \atop n}\right⟩_{α_{s}} = \binom{N − m}{n} x_{s}^{n}a_{s}^{N−m−n}.

For example, when t = 3, the product \overline{X} = α_{3}α_{2}α_{1} gives the matrix elements, for homogeneity of degree N,

\left⟨{m \atop n}\right⟩\overline{X} = ∑_{(k_{2},k_{3})} \left⟨{m \atop k_{3}}\right⟩_{α_{3}} \left⟨{k_{3} \atop k_{2}}\right⟩_{α_{2}} \left⟨{k_{2} \atop n}\right⟩_{α_{1}}
= ∑_{(k_{2},k_{3})} \binom{N − m}{k_{3}}\binom{N − k_{3}}{k_{2}}\binom{N − k_{2}}{n} x_{1}^{n}x_{2}^{k_{2}}x_{3}^{k_{3}}a_{1}^{N−k_{2}−n}a_{2}^{N−k_{3}−k_{2}}a_{3}^{N−k_{3}−m}.

Thus, the symmetric trace tr_{Sym}^{N}(\overline{X}) = ∑_{m} \left⟨{m \atop m}\right⟩\overline{X} is

∑_{(k_{1},k_{2},k_{3})} \binom{N − k_{2}}{k_{1}}\binom{N − k_{3}}{k_{2}}\binom{N − k_{1}}{k_{3}} x_{1}^{k_{1}}x_{2}^{k_{2}}x_{3}^{k_{3}} a_{1}^{N−k_{1}−k_{2}}a_{2}^{N−k_{2}−k_{3}}a_{3}^{N−k_{3}−k_{1}},

a cyclic binomial. In general, for a product of arbitrary length, the symmetric trace is given by the corresponding cyclic binomial.

Recall the recurrence

S_{N}(x) = 2x S_{N−1}(x) − S_{N−2}(x),  (25)

for N ≥ 1. The Chebyshev polynomials of the first kind, T_{N} = T_{N}(x), are solutions of this recurrence with initial conditions T_{−1} = x and T_{0} = 1, and the Chebyshev polynomials of the second kind, U_{N} = U_{N}(x), are solutions with U_{−1} = 0 and U_{0} = 1.

Combining these observations yields the main identities:

Theorem 4.4 Let \overline{X} = α_{t}α_{t−1} ⋯ α_{1}, with α_{s} =(\begin{matrix}0 & 1 \\ x_{s} & a_{s} \end{matrix}) for 1 ≤ s ≤ t, and

let \overline{τ} = tr(\overline{X}) and \overline{Δ} = det(\overline{X}). Let \overline{G}_{N} denote the first fundamental solution to the (\overline{τ}, \overline{Δ})-recurrence (22).

Then we have the cyclic binomial identity

\overline{G}_{N} = ∑_{(k_{1},...,k_{t})} \binom{N − k_{2}}{k_{1}}\binom{N − k_{3}}{k_{2}} ⋯ \binom{N − k_{1}}{k_{t}} x_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{t}^{k_{t}} a_{1}^{N−k_{1}−k_{2}}a_{2}^{N−k_{2}−k_{3}} ⋯ a_{t}^{N−k_{t}−k_{1}}
= \overline{Δ}^{N/2}U_{N} (\frac{\overline{τ}}{2\sqrt{\overline{Δ}}})
= ∑_{k=0}^{⌊N/2⌋} \binom{N − k}{k}\overline{τ}^{N−2k}(−\overline{Δ})^{k},

where U_{N} denotes the Chebyshev polynomial of the second kind.

Proof. The first equality follows by computing the symmetric trace for arbitrary t as indicated above. The second follows by induction on N using initial conditions \overline{G}_{−1} = 0 and \overline{G}_{0} = 1, the (\overline{τ}, \overline{Δ})-recurrence (22) and the Chebyshev recurrence (25). The third follows from the second by the Sym-

metric Trace Theorem applied to \overline{X} = (\begin{matrix}0 & 1 \\ −\overline{Δ} & \overline{τ} \end{matrix}), the shift matrix for the

(\overline{τ}, \overline{Δ})-recurrence.

Note that G_{−1} = 0 and G_{0} = 1, so G_{1} = τ using the (τ, Δ)-recurrence. This also follows directly from the condition k_{s−1} +k_{s} ≤ 1 for non-zero terms in the cyclic binomial summation above. Note also that setting all a_{s} = 1 above gives explicit expressions for G_{N}.

Example 5 Here N = 2 and t = 3. Let A^{Sym(N)} denote the symmetric representation in degree N of the matrix A. From the above we have

G_{2} = ∑_{(k_{1},k_{2},k_{3})} \binom{2 − k_{2}}{k_{1}}\binom{2 − k_{3}}{k_{2}}\binom{2 − k_{1}}{k_{3}} x_{1}^{k_{1}}x_{2}^{k_{2}}x_{3}^{k_{3}}
= 1 + 2x_{1} + 2x_{2} + 2x_{3} + x_{1}^{2} + 2x_{1}x_{2} + 2x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} + x_{3}^{2} + x_{1}x_{2}x_{3}.

Also d = 2, so \binom{N+d−1}{N} = 3, and ξ_{s} = (\begin{matrix}0 & 1 \\ x_{s} & 1 \end{matrix}) for 1 ≤ i ≤ 3, thus

X = ξ_{3}ξ_{2}ξ_{1} = (\begin{matrix}x_{1} & x_{2} + 1 \\ x_{1}x_{3} + x_{1} & x_{2} + x_{3} + 1 \end{matrix}) .

Now ξ_{s}^{Sym(2)} = (\begin{matrix}0 & 0 & 1 \\ 0 & x_{s} & 1 \\ x_{s}^{2} & 2x_{s} & 1 \end{matrix}) for 1 ≤ s ≤ 3, and so

X^{Sym(2)} = ξ_{3}^{Sym(2)}ξ_{2}^{Sym(2)}ξ_{1}^{Sym(2)}

= (\begin{matrix}x_{1}^{2} & 2x_{1}x_{2} + 2x_{1} & x_{2}^{2} + 2x_{2} + 1 \\ x_{1}^{2}x_{3} + x_{1}^{2} & {x_{1}x_{2}x_{3} + 2x_{1}x_{2} \atop +2x_{1}x_{3} + 2x_{1}} & {x_{2}^{2} + x_{2}x_{3} + 2x_{2} \atop +x_{3} + 1} \\ x_{1}^{2}x_{3}^{2} + 2x_{1}^{2}x_{3} + x_{1}^{2} & {2x_{1}x_{2}x_{3} + 2x_{1}x_{3}^{2} + 2x_{1}x_{2} \atop +4x_{1}x_{3} + 2x_{1}} & {x_{3}^{2} + 2x_{2}x_{3} + x_{2}^{2} \atop +2x_{2} + 2x_{3} + 1} \end{matrix} ) .

We check that G_{2} = tr(X^{Sym(2)}), as indicated above.

We now give an expression for G_{N} as a quotient of two matching polynomials; this requires (29) from the next section.

Theorem 4.5 For N ≥ 0 we have

G_{N} = \frac{Φ_{1,Nt−2}}{ϕ_{t−2}} .

Proof. Equation (29) is

Φ_{i,Nt+j} = Φ_{i,j} G_{N} − Δ ϕ_{i,j} G_{N−1},  (26)

and from Example 2 we have ϕ_{i,i−3} = 0. So (26) with j = i − 3 gives

G_{N} = \frac{Φ_{i,Nt+i−3}}{Φ_{i,i−3}} = \frac{Φ_{1,Nt−2}}{ϕ_{t−2}} ,  (27)

the second equality comes from putting i = 1 in the first and then using (9) in the denominator.

Finally, consider the Fibonacci sequence {F_{m} | m ≥ 1} = {1, 1, 2, 3, 5, 8, 13, 21, …}. It is straightforward to show that the number of matchings in the path P_{m} with m−1 edges is F_{m+1}. Now Φ_{1,Nt−2} is the matching polynomial of the path P (1, Nt−2) which has (N +1)t−2 edges and so has F_{(N+1)t} matchings. Similarly, the path whose matching polynomial is ϕ_{t−2} has F_{t} matchings. Now, evaluating (27) above with N = N − 1 and x_{s} = 1 for all 1 ≤ s ≤ t, gives F_{t}|F_{Nt}, a well-known result on Fibonacci numbers, see pp. 148-9, Hardy and Wright [4]. Furthermore, we have

\frac{F_{(N+1)t}}{F_{t}} = ∑_{(k_{1},...,k_{t})} \binom{N − k_{2}}{k_{1}}\binom{N − k_{3}}{k_{2}} ⋯ \binom{N − k_{1}}{k_{t}}.

5 Examples: Paths, Cycles, Trees

In this Section we express the matching polynomial of some well-known graphs in terms of the fundamental solutions to the (τ, Δ)-recurrence (12).

G_{N} is the first fundamental solution to the (τ, Δ)-recurrence, so the initial values for G_{N} are

G_{−2} = \frac{−1}{Δ}, G_{−1} = 0, G_{0} = 1, (and G_{1} = τ).  (28)

The second fundamental solution is −ΔG_{N−1}.

5.1 Paths

Φ_{i,Nt+j} satisfies the (τ, Δ)-recurrence whose fundamental solutions are G_{N} and −ΔG_{N−1}, thus Φ_{i,Nt+j} = a G_{N} + b (−ΔG_{N−1}) for some a and b. The initial conditions for Φ_{i,Nt+j} from (9) and for G_{N} from (28) give a = Φ_{i,j} and b = Φ_{i,−t+j} = ϕ_{i,j}. Hence for N ≥ −1,

Φ_{i,Nt+j} = Φ_{i,j} G_{N} − Δ ϕ_{i,j} G_{N−1}.  (29)

Example 6 Here i = 2 and t = 3,

\begin{matrix}N = −1 & ϕ_{2,2} = 1 + x_{2}, \\ N = 0 & ϕ_{2,3} = 1 + x_{2} + x_{3}, \\ N = 0 & Φ_{2,1} = 1 + x_{1} + x_{2} + x_{3} + x_{1}x_{2}, \\ N = 0 & Φ_{2,2} = 1 + x_{1} + 2x_{2} + x_{3} + x_{1}x_{2} + x_{2}^{2} + x_{2}x_{3}, \\ N = 1 & Φ_{2,3} = 1 + x_{1} + 2x_{2} + 2x_{3} + x_{1}x_{2} + x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} + x_{3}^{2} + x_{1}x_{2}x_{3}. \end{matrix}

For N ≥ 1 let P_{Nt+j+1} = P (1, (N − 1)t + j) be the path with Nt + j + 1 vertices and Nt + j edges, cyclically labelled starting with label x_{1}. Let P_{Nt+j+1}(x) = P_{Nt+j+1} = Φ_{1,(N−1)t+j} be its matching polynomial. With this notation any subscript on a P, P, C, or C refers to the number of vertices in the appropriate graph.

Theorem 5.1 For any N ≥ 1 we have

(i) P_{Nt+j+1} = Φ_{1,j} G_{N−1} − Δ ϕ_{j} G_{N−2},
(ii) P_{Nt+1} = G_{N} + (ϕ − τ) G_{N−1}.

Proof. The proof of (i) is clear using (29) with i = 1 and N = N − 1. So (i) with j = 0 gives P_{Nt+1} = Φ_{1,0} G_{N−1} − Δ ϕ_{0} G_{N−2}. But Φ_{1,0} = Φ_{1,−t+t} = ϕ_{1,t} = ϕ_{t} = ϕ and ϕ_{0} = ϕ_{1,0} = 1, and then using the (τ, Δ)-recurrence for G_{N} gives (ii).

Example 7 Here t = 3,

P_{1·3+2+1}  • x_{1} • x_{2} • x_{3} • x_{1} • x_{2} •

P_{1·3+2+1} = 1 + 2x_{1} + 2x_{2} + x_{3} + x_{1}^{2} + 2x_{1}x_{2} + x_{1}x_{3} + x_{2}^{2} + x_{2}x_{3} + x_{1}x_{2}x_{3}.

P_{2·3+1}  • x_{1} • x_{2} • x_{3} • x_{1} • x_{2} • x_{3} •

P_{2·3+1} = 1 + 2x_{1} + 2x_{2} + 2x_{3} + x_{1}^{2} + 2x_{1}x_{2} + 3x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} + x_{3}^{2} + x_{1}^{2}x_{3} + 2x_{1}x_{2}x_{3} + x_{1}x_{3}^{2}.

5.2 Cycles

Now we identify the first and the last vertices of the path P (i, Nt + j) to form the cyclically labelled cycle C(i, Nt + j) with matching polynomial Γ_{i,Nt+j}(x) = Γ_{i,Nt+j}.

By decomposing Γ_{i,Nt+j} at the ‘first’ edge labelled x_{i} we see that, cf. (29),

Γ_{i,Nt+j} = Φ_{i+1,Nt+j} + x_{i} Φ_{i+2,Nt+j−1},
= Φ_{i+1,j} G_{N} − Δ ϕ_{i+1,j} G_{N−1} + x_{i}{Φ_{i+2,j−1} G_{N} − Δ ϕ_{i+2,j−1} G_{N−1}},
= {Φ_{i+1,j} + x_{i} Φ_{i+2,j−1}} G_{N} − Δ {ϕ_{i+1,j} + x_{i} ϕ_{i+2,j−1}} G_{N−1},
= Γ_{i,j} G_{N} − Δ τ_{i,j} G_{N−1},  (30)

using (29) at the second line, and decomposing Γ_{i,j} and τ_{i,j} at the first edge x_{i} at the fourth line. Also, defining Γ_{i,−t+j} = τ_{i,j} ensures that (30) is true for all N ≥ −1.

Example 8 Here i = 2 and t = 3 again,

\begin{matrix}N = −1 & τ_{2,2} = 1, \\ N = 0 & τ_{2,3} = 1 + x_{2} + x_{3}, \\ N = 0 & Γ_{2,1} = 1 + x_{1} + x_{2} + x_{3}, \\ N = 0 & Γ_{2,2} = 1 + x_{1} + 2x_{2} + x_{3} + x_{1}x_{2} + x_{2}x_{3}, \\ N = 1 & Γ_{2,3} = 1 + x_{1} + 2x_{2} + 2x_{3} + x_{1}x_{2} + x_{1}x_{3} + x_{2}^{2} + x_{2}x_{3} + x_{3}^{2}. \end{matrix}

Let C_{Nt+j} = C(1, (N − 1)t + j) be the cycle with Nt + j vertices and Nt + j edges in which labelling has started with x_{1}, and let C_{Nt+j}(x) = C_{Nt+j} = Γ_{1,(N−1)t+j} be its matching polynomial. Compare with Theorem 5.1,

Theorem 5.2 For any N ≥ 1 we have

(i) C_{Nt+j} = Γ_{1,j} G_{N−1} − Δ τ_{j} G_{N−2},
(ii) C_{Nt} = G_{N} − Δ G_{N−2}.

Proof. The proof of (i) is clear from (30). Part (i) with j = 0 gives (ii), using Γ_{1,0} = τ, and τ_{0} = 2 from (8).

Example 9 Here t = 3 again, the cycle starts at the large vertex and proceeds clockwise, C_{1·3+2}

x_2 x_3 x_1 x_2 x_1

C_{1·3+2} = 1 + 2x_{1} + 2x_{2} + x_{3} + x_{1}^{2} + x_{1}x_{2} + x_{1}x_{3} + x_{2}^{2} + x_{2}x_{3}

C_{2·3}

x_3 x_1 x_2 x_3 x_1 x_2

C_{2·3} = 1 + 2x_{1} + 2x_{2} + 2x_{3} + x_{1}^{2} + 2x_{1}x_{2} + 2x_{1}x_{3} + x_{2}^{2} + 2x_{2}x_{3} + x_{3}^{2} + 2x_{1}x_{2}x_{3}.

For a fixed t ≥ 1 write P̂_{N} = P_{Nt+1} and Ĉ_{N} = C_{Nt}. We now express G_{N}, P̂_{N}, and Ĉ_{N} in terms of Chebyshev polynomials.

It is well-known that, in one variable x, the matching polynomial of the path P_{2m} is related to U_{2m} as follows

M(P_{2m}, x) = (−1)^{m}x^{m} U_{2m} (\frac{i}{2\sqrt{x}}) ,

and, for P_{2m−1} we have

M(P_{2m−1}, x) = (−1)^{m}x^{m} [U_{2m} (\frac{i}{2\sqrt{x}}) + U_{2m−2} (\frac{i}{2\sqrt{x}})] ,

where i = \sqrt{−1}. Also, for the matching polynomials M(C_{2m}) and M(C_{2m−1}) of the cycles C_{2m} and C_{2m−1} there are similar formulas but with a factor of 2 on the right-hand side where U is replaced by T. See Theorem 3 of Godsil and Gutman [3], and Theorems 9 and 11 of Farrell [1].

Now Theorem 4.4 modified for G_{N} gives

G_{N} = Δ^{N/2} U_{N} (\frac{τ}{2\sqrt{Δ}}) .  (31)

Formulas for P̂_{N} and Ĉ_{N} in terms of U_{N} and T_{N} are given below, where the variable t is suppressed.

Theorem 5.3 For any N ≥ 1 we have

(i) P̂_{N} = Δ^{N/2} \{U_{N} (\frac{τ}{2\sqrt{Δ}}) + (\frac{ϕ − τ}{\sqrt{Δ}} ) U_{N−1} (\frac{τ}{2\sqrt{Δ}})\} ,
(ii) Ĉ_{N} = 2Δ^{N/2} T_{N} (\frac{τ}{2\sqrt{Δ}}) .

Proof. (i) This follows from Theorem 5.1(ii) and (31). (ii) From Theorem 5.2(ii) we have Ĉ_{N} = G_{N} − ΔG_{N−2}, and now the wellknown relation 2T_{N} = U_{N} − U_{N−2} between the two types of Chebyshev polynomials and (31) gives the result.

Expressions for G_{N}, P̂_{N}, and Ĉ_{N} for N = 0, 1, 2, 3, and 4 are given below

G_{0} = 1  P̂_{0} = 1  Ĉ_{0} = 2
G_{1} = τ  P̂_{1} = ϕ  Ĉ_{1} = τ
G_{2} = τ^{2} − Δ  P̂_{2} = ϕτ − Δ  Ĉ_{2} = τ^{2} − 2Δ
G_{3} = τ^{3} − 2τΔ  P̂_{3} = ϕτ^{2} − ϕΔ − τΔ  Ĉ_{3} = τ^{3} − 3τΔ
G_{4} = τ^{4} − 3τ^{2}Δ + Δ^{2} P̂_{4} = ϕτ^{3} − 2ϕτΔ − τ^{2}Δ + Δ^{2} Ĉ_{4} = τ^{4} − 4τ^{2}Δ + 2Δ^{2}.

5.3 Trees

Here we consider cyclically labelled trees.

First let us extend the definition of a cyclically labelled path to include the path of Fig. 1, and the graph P_{1} with one vertex and no edges.

A tree is a connected simple graph with no cycles, and a rooted tree is a tree in which some vertex of degree 1 has been specified to be the root, r. Given any rooted tree, let us label its edges by first labelling the edge incident to r with x_{i}. Then label all edges incident to this edge with x_{i+1}, then label all edges incident to these edges with x_{i+2}, and so on until label x_{t} has been used. Then label with the ordered set {x_{1}, …, x_{t}} in a similar manner to before, repeating cyclically until all edges have been labelled,..., and so on. Let T denote such a cyclically labelled tree, see Fig. 5 for an example with i = 2 and t = 3.

x_{2} x_{3} x_{1} r  x_{3} x_{1} x_{1} x_{1} x_{2} x_{3} Fig. 5: A cyclically labelled tree with i = 2 and t = 3.

We may draw any such T with r as the leftmost vertex. Then we place the other vertices of T from ‘left to right’ according to their distance from r, i.e., if a vertex v_{1} is at distance d_{1} from r and vertex v_{2} is at distance d_{2} from r where d_{2} > d_{1}, then v_{2} is placed to the right of v_{1}.

Paths in T are of two types: (I) A path that always moves from left to right (a path that always moves from right to left can be thought of one that always moves from left to right): such a path is clearly cyclically labelled; or (II) a path that moves first from right to left and then from left to right; such a path must pass through at least one vertex of degree ≥ 3, i.e., a vertex where T ‘branches’.

Let V denote the set of vertices of degree ≥ 3 in T, and let v ∈ V be arbitrary of degree deg(v). Vertex v has 1 edge to its left and deg(v) − 1 ≥ 2 edges to its right. Let H_{v} be the subgraph of T that consists of the ‘last’ deg(v) − 2 ≥ 1 edges as we rotate clockwise around v. Thus H_{v} is the star K_{1,deg(v)−2} centered at v. Set H = ∪_{v∈V} H_{v}.

Lemma 5.4 The forest T − H is a union of cyclically labelled paths.

Proof. We show that T − H does not contain a path of type (II). Suppose it does contain a path of type (II), then this path must pass through some vertex v ∈ V. So 2 edges incident to v and to the right of v lie in this path and so lie in T − H, a contradiction because T − H contains only 1 edge incident to v and to the right of v. Thus T − H is a union of paths of type (I), each of which is a cyclically labelled path.

Thus T − H is a union of cyclically labelled paths, and so T − H − \overline{M}_{H} is also, for every matching M_{H} of H. We know the matching polynomial of any cyclically labelled path, so we can decompose the matching polynomial of T, M(T, x), at H, according to Theorem 1.1,

M(T, x) = ∑_{M_{H}} M_{H}(x) M(T − H − \overline{M}_{H}, x),

where the summation is over every matching M_{H} of H.

Example 10 See Fig. 5.

Here H =  • x_{1} • x_{1} •  • x_{3} •

H has 6 matchings with weights: 1, x_{1}, x_{1}, x_{3}, x_{1}x_{3}, and x_{1}x_{3}. Thus there are 6 terms in the decomposition, and M(T, x) is the sum of the following 6 terms:

1.ϕ_{1}ϕ_{2,3}Φ_{2,1}+x_{1}.ϕ_{1}ϕ_{2,2}ϕ_{2,3}+x_{1}.ϕ_{1}ϕ_{2,2}ϕ_{3,3}+x_{3}.ϕ_{1}ϕ_{2,3}+x_{1}x_{3}.ϕ_{2,3}+x_{1}x_{3}.ϕ_{3,3} = 1 + 4x_{1} + 2x_{2} + 3x_{3} + 3x_{1}^{2} + 7x_{1}x_{2} + 8x_{1}x_{3} + x_{2}^{2} + 3x_{2}x_{3} + 2x_{3}^{2} +5x_{1}^{2}x_{2} + 3x_{1}^{2}x_{3} + 3x_{1}x_{2}^{2} + 7x_{1}x_{2}x_{3} + 4x_{1}x_{3}^{2} + 2x_{1}^{2}x_{2}^{2} + 3x_{1}^{2}x_{2}x_{3}.

Acknowledgement: We thank the referees for some helpful comments.

References

[1] E.J. Farrell, An Introduction to Matching Polynomials, Jour. Comb. Theory, Series B, 27, pp. 75–86, 1979.

[2] W. Fulton, J. Harris, Representation Theory, A First Course, Graduate Texts in Mathematics, 129, Springer-Verlag, 1991.

[3] C.D. Godsil, I. Gutman, On the Theory of the Matching Polynomial, Jour. Graph. Theory, 5, pp. 137–144, 1981.

[4] G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, 5th Edition, Oxford University Press, 1979.

[5] T.A. Springer, Invariant Theory, Lecture Notes in Mathematics, 585, Springer-Verlag, 1977.