GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH
BUNDLES
DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
Abstract. In this paper, we find computational formulae for generalized characteristic
polynomials of graph bundles. We show that the number of spanning trees in a graph is
the partial derivative (at (0, 1)) of the generalized characteristic polynomial of the graph.
Since the reciprocal of the Bartholdi zeta function of a graph can be derived from the
generalized characteristic polynomial of a graph, consequently, the Bartholdi zeta function
of a graph bundle can be computed by using our computational formulae.
1. Introduction
One of classical invariants in graph theory is the characteristic polynomial which comes
from the adjacency matrices. It displays not only graph theoretical properties but also
algebraic prospectives, such as spectra of graphs. There have been many meaningful gener-
alizations of characteristic polynomials [5,12]. In particular, we are interested in one found
by Cvetkovic and alt. as a polynomial on two variables [5],
FG(λ, µ) = det(λI − (A(G)− µD(G))).
The zeta functions of finite graphs [1, 2, 8] feature of Riemanns zeta functions and can
be considered as an analogue of the Dedekind zeta functions of a number field. It can
be expressed as the determinant of a perturbation of the Laplacian and a counterpart of
the Riemann hypothesis [19]. Bartholdi introduced the Bartholdi zeta function ZG(u, t)
of a graph G together with a comprehensive overview and problems on the Bartholdi zeta
functions [1]. He also showed that the reciprocal of the Bartholdi zeta function of G is
ZG(u, t)
1− (1− u)2t2
)εG−νG
I − A(G)t+ (1− u)(DG − (1− u)I)t
Kwak and alt. studied the Bartholdi zeta functions of some graph bundles having regular
fibers [11]. Mizuno and Sato also studied the zeta function and the Bartholdi zeta function
of graph coverings [13,15]. Recently, it was shown that the Bartholdi zeta function ZG(u, t)
can be found as the reciprocal of the generalized characteristic polynomials FG(λ, µ) with
a suitable substitution [9].
The aim of the present article is to find computational formulae for generalized char-
acteristic polynomials FG(λ, µ) of graph bundles and its applications. For computational
formulae, we show that if the fiber of the graph bundle is a Schreier graph, the conjugate
class of the adjacency matrix has a representative whose characteristic polynomial can be
2000 Mathematics Subject Classification. 05C50, 05C25, 15A15, 15A18.
Key words and phrases. generalized characteristic polynomials, graph bundles, the Bartholdi zeta
functions.
This research was supported by the Yeungnam University research grants in 2007.
http://arxiv.org/abs/0704.1431v1
2 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
computed efficiently using the representation theory of the symmetric group. We also pro-
vide computational formulae for generalized characteristic polynomials of graph bundles
G ×φ F where the images of φ lie in an abelian subgroup Γ of Aut(F ). To demonstrate
the efficiency of our computation formulae, we calculate the generalized characteristic poly-
nomials FG of some Kn-bungles G ×
φ Kn. Consequently, we can obtain the generalized
characteristic polynomials FK1,m×Kn(λ, µ) of K1,m ×Kn which is a standard model of net-
work with hubs. Its adjacency matrix, known as a “kite”, is one of important examples in
matrix analysis.
The outline of this paper is as follows. First, we review the terminology of the generalized
characteristic polynomials and show that the number of spanning trees in a graph is the
partial derivative (at (0, 1)) of the generalized characteristic polynomial of the given graph
in section 2. Next, we study a similarity of the adjacency matrices of graph bundles and find
computational formulae for generalized characteristic polynomial FG(λ, µ) of graph bundles
in section 3. In section 4, we find the generalized characteristic polynomial of K1,m ×Kn
and find the number of spanning trees of K1,m ×Kn.
2. Generalized characteristic polynomials and complexity
In the section, we review the definitions and useful properties of the generalized charac-
teristic polynomials and find the number of spanning trees in a graph using the generalized
characteristic polynomials.
Let G be an undirected finite simple graph with vertex set V (G) and edge set E(G).
Let νG and εG denote the number of vertices and edges of G, respectively. An adjacency
matrix A(G) = (aij) is the νG×νG matrix with aij = 1 if vi and vj are adjacent and aij = 0
otherwise. The degree matrix D(G) of G is the diagonal matrix whose (i, i)-th entry is
the degree dGi = degG(vi) of vi in G for each 1 ≤ i ≤ νG. The complexity κ(G) of G is
the number of spanning trees in G. An automorphism of G is a permutation of the vertex
set V (G) that preserves the adjacency. By |X|, we denote the cardinality of a finite set
X . The set of automorphisms forms a permutation group, called the automorphism group
Aut(G) of G. The characteristic polynomial of G, denoted by Φ(G;λ), is the characteristic
polynomial det(λI − A(G)) of A(G). Cvetkovic and alt. introduced a polynomial on two
variables of G, FG(λ, µ) = det(λI − (A(G) − µD(G))) as a generalization of characteristic
polynomials of G [5], for example, the characteristic polynomial of G is FG(λ, 0) and the
characteristic polynomial of the Laplacian matrix D(G)− A(G) of G is (−1)νGFG(−λ, 1).
In [9]], it was shown that the Bartholdi zeta function ZG(u, t) of a graph can be obtained
from the polynomial FG(λ, µ) with a suitable substitution as follows.
ZG(u, t)
1− (1− u)2t2
)εG−νG
tνGFG
− (1− u)2t, (1− u)t
FG(λ, µ) =
(1− µ2)εG
1− µ2
1− µ2
The complexities for various graphs have been studied [13,16]. In particular, Northshield
showed that the complexity of a graph G can be given by the derivative
f ′G(1) = 2(εG − νG) κ(G)
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 3
of the function fG(u) = det[I − u A(G) + u
2 (D(G)− I)], for a connected graph G [16]. By
considering the idea of taking the derivative, we find that the complexity of a finite graph can
be expressed as the partial derivative of the generalized characteristic polynomial FG(λ, µ)
evaluated at (0, 1).
Theorem 2.1. Let FG(λ, µ) = det(λI − (A(G)− µD(G))) be the generalized characteristic
polynomial of a graph G. Then the number of spanning trees in G, κ(G), is
|(0,1),
where εG is the number of edges of G.
Proof. Let Bλ,µ = λI − (A(G) − µD(G)) = ((bλ,µ)ij) and let B
λ,µ = ((bλ,µ)
ij) denote the
matrix Bλ,µ with each entry of k-th row replace the corresponding partial derivative with
respect to µ. Then
(det Bλ,µ) =
sgn(σ)
((bλ,µ)iσ(i))
(bλ,µ)
iσ(i)) =
(det Bkλ,µ).
Since (b0,1)
ij = d
i δij + aij(δkj − 1) = diδij − aij + aijδki,
|(0,1) =
det (B0,1 + aij(δki)).
Let (Mk)ij = aijδki and let (C0,1)ij be the cofactor of bij in B0,1. Then
det (B0,1 +M
(B0,1 +M
k)kj(−1)
k+j(C0,1)kj = dk (C0,1)kk.
Since det B0,1 = 0, (C0,1)ij = κ(G) for all i and j [3]. Hence,
|(0,1) =
dk (C0,1)kk = κ(G)
dk = 2 εGκ(G).
Thus,
κ(G) =
|(0,1).
3. Generalized characteristic polynomials of graph bundles
Let G be a connected graph and let ~G be the digraph obtained from G by replacing each
edge of G with a pair of oppositely directed edges. The set of directed edges of ~G is denoted
by E( ~G). By e−1, we mean the reverse edge to an edge e ∈ E( ~G). We denote the directed
edge e of ~G by uv if the initial and the terminal vertices of e are u and v, respectively.
For a finite group Γ, a Γ-voltage assignment of G is a function φ : E( ~G) → Γ such that
φ(e−1) = φ(e)−1 for all e ∈ E( ~G). We denote the set of all Γ-voltage assignments of G by
C1(G; Γ).
4 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
Let F be another graph and let φ ∈ C1(G; Aut(F )). Now, we construct a graph G×φ F
with the vertex set V (G ×φ F ) = V (G) × V (F ), and two vertices (u1, v1) and (u2, v2) are
adjacent in G ×φ F if either u1u2 ∈ E( ~G) and v2 = v
φ(u1u2)
1 = v1φ(u1u2) or u1 = u2 and
v1v2 ∈ E(F ). We call G ×
φ F the F -bundle over G associated with φ (or, simply a graph
bundle) and the first coordinate projection induces the bundle projection pφ : G ×φ F →
G. The graphs G and F are called the base and the fibre of the graph bundle G ×φ F ,
respectively. Note that the map pφ maps vertices to vertices, but the image of an edge can
be either an edge or a vertex. If F = Kn, the complement of the complete graph Kn of n
vertices, then an F -bundle over G is just an n-fold graph covering over G. If φ(e) is the
identity of Aut(F ) for all e ∈ E( ~G), then G ×φ F is just the Cartesian product of G and
F , a detail can be found in [10].
Let φ be an Aut(F )-voltage assignment of G. For each γ ∈ Aut(F ), let ~G(φ,γ) denote
the spanning subgraph of the digraph ~G whose directed edge set is φ−1(γ). Thus the
digraph ~G is the edge-disjoint union of spanning subgraphs ~G(φ,γ), γ ∈ Aut(F ). Let V (G) =
{u1, u2, . . . , uνG} and V (F ) = {v1, v2, . . . , vνF }. We define an order relation ≤ on V (G×
as follows: for (ui, vk), (uj, vℓ) ∈ V (G ×
φ F ), (ui, vk) ≤ (uj, vℓ) if and only if either k < ℓ
or k = ℓ and i ≤ j. Let P (γ) denote the νF × νF permutation matrix associated with
γ ∈ Aut(F ) corresponding to the action of Aut(F ) on V (F ), i.e., its (i, j)-entry P (γ)ij = 1
if γ(vi) = vj and P (γ)ij = 0 otherwise. Then for any γ, δ ∈ Aut(F ), P (δγ) = P (δ)P (γ).
Kwak and Lee expressed the adjacency matrix A(G ×φ F ) of a graph bundle G ×φ F as
follows.
Theorem 3.1 ( [10]). Let G and F be graphs and let φ be an Aut(F )-voltage assignment
of G. Then the adjacent matrix of the F -bundle G×φ F is
A(G×φ F ) =
γ∈Aut(F )
P (γ)⊗A( ~G(φ,γ))
 + A(F )⊗ IνG ,
where P (γ) is the νF × νF permutation matrix associated with γ ∈ Aut(F ) corresponding to
the action of Aut(F ) on V (F ), and IνG is the identity matrix of order νG.
For any finite group Γ, a representation ρ of a group Γ over the complex numbers is a
group homomorphism from Γ to the general linear group GL(r,C) of invertible r×r matrices
over C. The number r is called the degree of the representation ρ [18]. Suppose that Γ ≤ Sn
is a permutation group on Ω. It is clear that P : Γ → GL(r,C) defined by γ → P (γ), where
P (γ) is the permutation matrix associated with γ ∈ Γ corresponding to the action of Γ on
Ω, is a representation of Γ. It is called the permutation representation. Let ρ1 = 1, ρ2, . . . , ρℓ
be the irreducible representations of Γ and let fi be the degree of ρi for each 1 ≤ i ≤ ℓ,
where f1 = 1 and
i=1 f
i = |Γ|. It is well-known that the permutation representation P
can be decomposed as the direct sum of irreducible representations : ρ = ⊕ℓi=1miρi [18]. In
other words, there exists an unitary matrix M of order |Γ| such that
M−1P (γ)M =
(Imi ⊗ ρi(γ)) (2)
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 5
for any γ ∈ Γ, where mi ≥ 0 is the multiplicity of the irreducible representation ρi in
the permutation representation P and
i=1mifi = νF . Notice that m1 ≥ 1 because it
represents the number of orbits under the action of the group Γ.
It is not hard to show that
(M ⊗ IνG)
−1A(G×φ F )(M ⊗ IνG) =
Imi ⊗ ρi(γ)⊗ A(
~G(φ,γ))
+ A(F )⊗ IνG .
For any vertex (ui, vk) ∈ V (G ×
φ F ), its degree is dGi + d
k , where d
i = degG(ui) and
dFk = degF (vk). Then, by our construction of D(G×
φ F ), the diagonal matrix D(G×φ F )
is equal to IνF ⊗D(G) +D(F )⊗ IνG and thus
(M ⊗ IνG)
−1D(G×φ F )(M ⊗ IνG) = IνF ⊗D(G) +D(F )⊗ IνG .
Therefore, the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µD(G)
+ (A(F )− µD(F ))⊗ IνG.
By summarizing these, we obtain the following theorem.
Theorem 3.2. Let G and F be two connected graphs and let φ be an Aut(F )-voltage
assignment of G. Let Γ be the subgroup of the symmetric group Sn. Furthermore, let ρ1 =
1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ, respectively.
Then the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µD(G)
+ (A(F )− µD(F ))⊗ IνG,
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
A graph F is called a Schreier graph if there exists a subset S of SνF such that S
−1 = S
and the adjacency matrix A(F ) of F is
s∈S P (s). We call such an S the connecting set
of the Schreier graph F . Notice that a Schreier graph with connecting set S is a regular
graph of degree |S| and most regular graphs are Schreier graphs [7, Section 2.3]. The
definition of the Schreier graph here is different that of original one. But, they are basically
identical [7, Section 2.4]. Clearly, every Cayley graph is a Schreier graph.
Theorem 3.3. Let G be a connected graph and let F be a Schreier graph with connecting
set S. Let φ : E( ~G) → Aut(F ) be a permutation voltage assignment. Let Γ be the subgroup
of the symmetric group SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Furthermore,
let ρ1 = 1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ,
respectively. Then the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
γ∈Aut(F )
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µ(D(G) + |S|IνG) +
ρi(s)
⊗ IνG
6 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
Proof. Let F be a Schreier graph with a connecting set S. Then the adjacency matrix of
F is A(F ) =
s∈S P (s). Hence, for any voltage assignment φ : E(
~G) → Aut(F ), one can
see that
A(G×φ F ) =
γ∈Aut(F )
P (γ)⊗ A( ~G(φ,γ))
P (s)⊗ IνG.
Let Γ be the subgroup of SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Since F is a regular
graph of degree |S|, one can see that
D(G×φ F ) = IνF ⊗ (D(G) + |S|IνG).
Now, one can have that the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
γ∈Aut(F )
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µ(D(G) + |S|IνG) +
ρi(s)
⊗ IνG
It is easy to see that the following theorem follows immediately from Theorem 3.3.
Theorem 3.4. Let G be a connected graph and let F be a Schreier graph with connecting
set S. Let φ : E( ~G) → Aut(F ) be a permutation voltage assignment. Let Γ be the subgroup
of the symmetric group SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Furthermore,
let ρ1 = 1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ,
respectively. Then the characteristic polynomial FG×φF (λ, µ) of a graph bundle G×
φ F is
Ifi ⊗ [(λ+ µ|S|)IνG + µD(G)] −
γ∈Aut(F )
ρi(γ)⊗A( ~G(φ,γ))−
ρi(s)
⊗ IνG
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
Let F = Kn be the trivial graph on n vertices. Then any Aut(Kn)-voltage assignment is
just a permutation voltage assignment defined in [7], and G ×φ Kn = G
φ is just an n-fold
covering graph of G. In this case, it may not be a regular covering. Now, the following
comes from Theorem 3.2.
Corollary 3.5. Let G be a connected graph and let F = Kn. The characteristic polynomial
FGφ(λ, µ) of the connected covering G
φ of a graph G derived from a permutation voltage
assignment φ : E( ~G) → Sn is
FG(λ, µ)×
Ifi ⊗ [(λ+ r)IνG + µD(G)]−
ρi(γ)⊗A( ~G(φ,γ))−
ρi(s)
⊗ IνG
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = n. �
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 7
Next, we consider the characteristic polynomial depending on two variable of graph bun-
dles G×φ F where the images of φ lie in an abelian subgroup Γ of Aut(F ) and the fiber F
is r-regular. In this case, for any γ1, γ2 ∈ Γ, the permutation matrices P (γ1) and P (γ2) are
commutative and DF = rIνF .
It is well-known (see [3]) that every permutation matrix P (γ) commutes with the adja-
cency matrix A(F ) of F for all γ ∈ Aut(F ). Since the matrices P (γ), γ ∈ Γ, and A(F ) are
all diagonalizable and commute with each other, they can be diagonalized simultaneously.
i.e., there exists an invertible matrix MΓ such that M
Γ P (γ)MΓ and M
Γ A(F )MΓ are di-
agonal matrices for all γ ∈ Γ. Let λ(γ,1), . . . , λ(γ,νF ) be the eigenvalues of the permutation
matrix P (γ) and let λ(F,1), . . . , λ(F,νF ) be the eigenvalues of the adjacency matrix A(F ).
M−1Γ P (γ)MΓ =
λ(γ,1) 0
. . .
0 λ(γ,νF )
 and M−1Γ A(F )MΓ =
λ(F,1) 0
. . .
0 λ(F,νF )
Using these similarities, we find that
(MΓ ⊗ IνG)
P (γ)⊗A( ~G(φ,γ)) + A(F )⊗ IνG
(MΓ ⊗ IνG)
λ(γ,i)A( ~G(φ,γ)) + λ(F,i)IνG
Recall that
(M ⊗ IνG)
−1D(G×φ F )(M ⊗ IνG)
= IνF ⊗D(G) + rIνF ⊗ IνG =
(D(G) + rIνG).
By summarizing these facts, we find the following theorem.
Theorem 3.6. Let G be a connected graph and let F be a connected regular graph of degree
r. If the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of Aut(F ), then the matrix
A(G×φ F )− µD(G×φ F ) is similar to
(λ(F,i) − rµ)IνG +
λ(γ,i)A( ~G(φ,γ))− µD(G)
Notice that the Cartesian product G × F of two graphs G and F is a F -bundle over
G associated with the trivial voltage assignment φ, i.e., φ(e) = 1 for all e ∈ E( ~G) and
A(G) = A( ~G). The following corollary comes from this observation.
Corollary 3.7. For any connected graph G and a connected r-regular graph F , the matrix
A(G× F )− µD(G× F ) of the cartesian product G× F is similar to
8 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
(λ(F,i) − rµ)IνG+ (A(G)−µD(G))
In particular, if G is a regular graph of degree dG, then the matrix A(G× F )− µD(G× F )
of the cartesian product G× F is
λ(F,i) + λ(G,j) − (r + d)µ
where λ(G,j) (1 ≤ j ≤ νG) and λ(F,i) (1 ≤ i ≤ νF ) are the eigenvalues of G and F ,
respectively. �
Now, we consider the case the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of
Aut(F ). A vertex-and-edge weighted digraph is a pair Dω = (D,ω), where D is a digraph
and ω : V (D)
E(D) → C is a function. We call ω the vertex-and-edge weight function on
D. Moreover, if ω(e−1) = ω(e), the complex conjugate of ω(e), for each edge e ∈ E(D), we
say that ω is symmetric. Given any vertex-and-edge weighted digraph Dω, the adjacency
matrix A(Dω) = (aij) of Dω is a square matrix of order | V (D) | defined by
aij =
e∈E({vi},{vj})
ω(e),
and the degree matrix DDω is the diagonal matrix whose (i, i)-th entry is ω(vi). We define
FDω(λ, µ) = det (λI − (A(Dω)− µDDω)) .
For any Γ-voltage assignment φ of G, let ωi(φ) : V ( ~G)
E( ~G) → C be the function defined
ωi(φ)(v) = degG(v), ωi(φ)(e) = λ(φ(e),i)
for e ∈ E( ~G) and v ∈ V ( ~G) where i = 1, 2, . . . , νF . Using Theorem 3.6, we have the
following theorem.
Theorem 3.8. Let G be a connected graph and let F be a connected regular graph of degree
r. If the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of Aut(F ), then the
characteristic polynomial FG×φF (λ, µ) of a graph bundle G×
φ F is
F ~Gωi(φ)
(λ+ rµ− λ(F,i), µ).
Now, the following corollary follows immediately from Corollary 3.7.
Corollary 3.9. For any connected graph G and a connected r-regular graph F , the char-
acteristic polynomial FG×F (λ, µ) of the cartesian product G× F is
FG(λ+ rµ− λ(F,i), µ).
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 9
In particular, if G is a regular graph of degree dG, then the characteristic polynomial
FG×F (λ, µ) of the cartesian product G× F is
λ+ (r + d)µ− λ(G,j) − λ(F,i)
where λ(G,j) (1 ≤ j ≤ νG) and λ(F,i) (1 ≤ i ≤ νF ) are the eigenvalues of G and F ,
respectively. �
4. Generalized characteristic polynomial of K1,m ×Kn
In this section, we find the generalized characteristic polynomial of K1,m ×Kn and find
the number of spanning trees of K1,m ×Kn. As we mentioned in introduction, K1,m ×Kn
is a typical model for networks with hubs thus, we will count its spanning trees. Since Kn
features many nice structures, we discuss the generalized characteristic polynomial of graph
bundles with a fiber, Cayley graph.
Let A be a finite group with identity idA and let S be a set of generators for A with
the properties that S = S−1 and idA 6∈ S, where S
−1 = {x−1 | x ∈ Ω}. The Cayley graph
Cay(A, S) is a simple graph whose vertex-set and edge-set are defined as follows:
V (Cay(A, S)) = A and E(Cay(A, S)) = {{g, h} | g−1h ∈ S}.
From now on, we assume that A is an abelian group of order n. Let G be a graph and
let φ : E( ~G) → A be an A-voltage assignment. Notice that the left action A on the vertex
set A of Cay(A, S) gives a group homomorphism from A to Aut(Cay(A, S)). Let P be the
permutation representation of A corresponding to the action. Then the map φ̃ : E( ~G) →
Aut(Cay(A, S)) defined by φ̃(e) = P (φ(e)) for any e ∈ E( ~G) is an Aut(Cay(A, S))-voltage
assignment. We also denote it φ. Notice that every irreducible representation of an abelian
group is linear. For convenience, let χ1 be the principal character of A and χ2, . . . , χn be
the other n− 1 irreducible characters of A. Now, by Theorem 3.3, we have that the matrix
A(G×φ Cay(A, S))− µD(G×φ Cay(A, S)) is similar to
|S|(1− µ))IνG +
A( ~G)− µD(G)
(χi(S)− |S|µ) IνG +
χi(γ)A( ~G(φ,γ))− µD(G)
where χi(S) =
χi(s) for each i = 2, 3, . . . , n. By Theorem 3.8, we have that the
characteristic polynomial FG×φCay(A,S)(λ, µ) of a graph bundle G×
φ Cay(A, S) is
FG(λ+ |S|(µ− 1), µ)×
F ~Gωi(φ)
(λ+ |S|µ− χi(S), µ),
where ωi(φ) : V ( ~G)
E( ~G) → C be the function defined by
ωi(φ)(v) = degG(v), ωi(φ)(e) = χi(φ(e))
10 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
for e ∈ E( ~G) and v ∈ V ( ~G) where i = 2, 3, . . . , n. Let Kn be the complete graph on n
vertices. Then Kn is isomorphic to Cay(A,A− {idA}) for any group A of order n. Since
χ1(A− {idA}) = n− 1 and χi(A− {idA}) = −1 for each i = 2, 3, . . . , n, we have
FG×φKn(λ, µ) = FG(λ+ (n− 1)(µ− 1), µ)×
F ~Gωi(φ)
(λ+ (n− 1)µ+ 1, µ).
Moreover over if φ is the trivial voltage assignment, then
FG×Kn(λ, µ) = FG(λ+ (n− 1)(µ− 1), µ)× FG(λ+ (n− 1)µ+ 1, µ)
Let G be the complete bipartite graph K1,m which also called a star graph. Notice that
K1,m is a tree and hence every graph bundle K1,m ×
φ F is isomorphic to the cartesian
product K1,m × F of K1,m and F . It is known [9] that for any natural numbers s and t
FKs,t(λ, µ) = (λ+ tµ)
s−1(λ+ sµ)t−1 [(λ+ sµ)(λ+ tµ)− st]
and hence FK1,m(λ, µ) = (λ+ µ)
m−1 [(λ+ µ)(λ+mµ)−m]. Now, we can see that
FK1,m×φKn(λ, µ)
= FK1,m(λ+ (n− 1)(µ− 1), µ)× FK1,m(λ+ (n− 1)µ+ 1, µ)
= [λ+ nµ− (n− 1)]m−1 {[λ + nµ− (n− 1)][λ+ (m+ n− 1)µ− (n− 1)]−m}
×[λ + nµ+ 1](m−1)(n−1) {[λ+ nµ+ 1][λ+ (m+ n− 1)µ+ 1]−m}
Now, by applying Theorem 2.1, we have that the number of spanning trees of K1,m ×Kn
κ(K1,m ×Kn) = n
n−2(m+ n+ 1)n+1(n+ 1)(m−1)(n−1).
References
[1] L. Bartholdi, Counting pathes in graphs, Enseign. Math., 45 (1999), 83–131.
[2] H. Bass, The Ihara.Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717–797.
[3] N. Biggs, Algebraic Graph Theory, 2nd ed Cambridge University Press, London, 1993.
[4] R. Brualdi and H. Ryser, Combinatorial matrix theory, Cambrige Univ. Press, Cambridge, 1991.
[5] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, NewYork, 1979.
[6] Y. Chae, J. H. Kwak, and J. Lee, Characteristic polynomials of some graph bundles, J. Korean Math.
Soc. 30 (1993), 229–249.
[7] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, New York 1987.
[8] Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math.
Soc. Japan 18 (1966), 219–235.
[9] H. K. Kim and J. Lee, A generalized characteristic polynomial of a graph having a semifree action,
Discrete Mathematics, to appear.
[10] J. H. Kwak and J. Lee, Characteristic polynomials of some graph bundles II, Linear and Multilinear
Algebra 32 (1992), 61–73.
[11] J. H. Kwak, J. Lee, M. Y. Sohn, Bartholdi zeta functions of graph bundles having regular fibers ,
European Journal of Combinatories 26 (2005), 593–605.
[12] R. Lipton, N. Vishnoi and Z. Zalcstein, A Generalization of the Characteristic Polynomial of a Graph,
CC Technical Report; GIT-CC-03-51, http://citeseer.ist.psu.edu/642697.html
[13] H. Mizuno and I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory
Ser. B, 89 (2003), 17–26.
http://citeseer.ist.psu.edu/642697.html
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 11
[14] H. Mizuno and I. Sato, Zeta functions of graph coverings, J. Combin. Theory Ser. B, 80 (2000),
247–257.
[15] H. Mizuno and I. Sato, Bartholdi zeta functions of graph coverings, J. Combin. Theory Ser. B, 89
(2003), 27–41.
[16] S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B, 74 (1998), 408–410.
[17] C. Oliveira, N. Maia de Abreu and S. Jurkiewicz, The characteristic polynomial of the Laplacian of
graphs in (a, b)-linear classes, Linear Algebra and its Applications, 356(1) (2002), 113–121.
[18] J.-P. Serre, Linear Representations of Finite Groups, Springer-Verlag, New York, 1977.
[19] H. Stark, A. Terras, Zeta functions of finite graphs and coverings, Adv. Math. 121 (1996), 126–165.
Department of Mathematics, Kyungpook National University, Taegu, 702-201 Korea
E-mail address : dongseok@knu.ac.kr
Mathematics, Catholic University of Taegu, Kyongsan, 712-702 Korea
E-mail address : hkkim@cu.ac.kr
Department of Mathematics, Yeungnam University, Kyongsan, 712-749, Korea
E-mail address : julee@yu.ac.kr
	1. Introduction
	2. Generalized characteristic polynomials and complexity
	3. Generalized characteristic polynomials of graph bundles
	4. Generalized characteristic polynomial of K1,mKn
	References

  In this paper, we find computational formulae for generalized characteristic
polynomials of graph bundles. We show that the number of spanning trees in a
graph is the partial derivative (at (0,1)) of the generalized characteristic
polynomial of the graph. Since the reciprocal of the Bartholdi zeta function of
a graph can be derived from the generalized characteristic polynomial of a
graph, consequently, the Bartholdi zeta function of a graph bundle can be
computed by using our computational formulae.

Introduction
One of classical invariants in graph theory is the characteristic polynomial which comes
from the adjacency matrices. It displays not only graph theoretical properties but also
algebraic prospectives, such as spectra of graphs. There have been many meaningful gener-
alizations of characteristic polynomials [5,12]. In particular, we are interested in one found
by Cvetkovic and alt. as a polynomial on two variables [5],
FG(λ, µ) = det(λI − (A(G)− µD(G))).
The zeta functions of finite graphs [1, 2, 8] feature of Riemanns zeta functions and can
be considered as an analogue of the Dedekind zeta functions of a number field. It can
be expressed as the determinant of a perturbation of the Laplacian and a counterpart of
the Riemann hypothesis [19]. Bartholdi introduced the Bartholdi zeta function ZG(u, t)
of a graph G together with a comprehensive overview and problems on the Bartholdi zeta
functions [1]. He also showed that the reciprocal of the Bartholdi zeta function of G is
ZG(u, t)
1− (1− u)2t2
)εG−νG
I − A(G)t+ (1− u)(DG − (1− u)I)t
Kwak and alt. studied the Bartholdi zeta functions of some graph bundles having regular
fibers [11]. Mizuno and Sato also studied the zeta function and the Bartholdi zeta function
of graph coverings [13,15]. Recently, it was shown that the Bartholdi zeta function ZG(u, t)
can be found as the reciprocal of the generalized characteristic polynomials FG(λ, µ) with
a suitable substitution [9].
The aim of the present article is to find computational formulae for generalized char-
acteristic polynomials FG(λ, µ) of graph bundles and its applications. For computational
formulae, we show that if the fiber of the graph bundle is a Schreier graph, the conjugate
class of the adjacency matrix has a representative whose characteristic polynomial can be
2000 Mathematics Subject Classification. 05C50, 05C25, 15A15, 15A18.
Key words and phrases. generalized characteristic polynomials, graph bundles, the Bartholdi zeta
functions.
This research was supported by the Yeungnam University research grants in 2007.
http://arxiv.org/abs/0704.1431v1
2 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
computed efficiently using the representation theory of the symmetric group. We also pro-
vide computational formulae for generalized characteristic polynomials of graph bundles
G ×φ F where the images of φ lie in an abelian subgroup Γ of Aut(F ). To demonstrate
the efficiency of our computation formulae, we calculate the generalized characteristic poly-
nomials FG of some Kn-bungles G ×
φ Kn. Consequently, we can obtain the generalized
characteristic polynomials FK1,m×Kn(λ, µ) of K1,m ×Kn which is a standard model of net-
work with hubs. Its adjacency matrix, known as a “kite”, is one of important examples in
matrix analysis.
The outline of this paper is as follows. First, we review the terminology of the generalized
characteristic polynomials and show that the number of spanning trees in a graph is the
partial derivative (at (0, 1)) of the generalized characteristic polynomial of the given graph
in section 2. Next, we study a similarity of the adjacency matrices of graph bundles and find
computational formulae for generalized characteristic polynomial FG(λ, µ) of graph bundles
in section 3. In section 4, we find the generalized characteristic polynomial of K1,m ×Kn
and find the number of spanning trees of K1,m ×Kn.
2. Generalized characteristic polynomials and complexity
In the section, we review the definitions and useful properties of the generalized charac-
teristic polynomials and find the number of spanning trees in a graph using the generalized
characteristic polynomials.
Let G be an undirected finite simple graph with vertex set V (G) and edge set E(G).
Let νG and εG denote the number of vertices and edges of G, respectively. An adjacency
matrix A(G) = (aij) is the νG×νG matrix with aij = 1 if vi and vj are adjacent and aij = 0
otherwise. The degree matrix D(G) of G is the diagonal matrix whose (i, i)-th entry is
the degree dGi = degG(vi) of vi in G for each 1 ≤ i ≤ νG. The complexity κ(G) of G is
the number of spanning trees in G. An automorphism of G is a permutation of the vertex
set V (G) that preserves the adjacency. By |X|, we denote the cardinality of a finite set
X . The set of automorphisms forms a permutation group, called the automorphism group
Aut(G) of G. The characteristic polynomial of G, denoted by Φ(G;λ), is the characteristic
polynomial det(λI − A(G)) of A(G). Cvetkovic and alt. introduced a polynomial on two
variables of G, FG(λ, µ) = det(λI − (A(G) − µD(G))) as a generalization of characteristic
polynomials of G [5], for example, the characteristic polynomial of G is FG(λ, 0) and the
characteristic polynomial of the Laplacian matrix D(G)− A(G) of G is (−1)νGFG(−λ, 1).
In [9]], it was shown that the Bartholdi zeta function ZG(u, t) of a graph can be obtained
from the polynomial FG(λ, µ) with a suitable substitution as follows.
ZG(u, t)
1− (1− u)2t2
)εG−νG
tνGFG
− (1− u)2t, (1− u)t
FG(λ, µ) =
(1− µ2)εG
1− µ2
1− µ2
The complexities for various graphs have been studied [13,16]. In particular, Northshield
showed that the complexity of a graph G can be given by the derivative
f ′G(1) = 2(εG − νG) κ(G)
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 3
of the function fG(u) = det[I − u A(G) + u
2 (D(G)− I)], for a connected graph G [16]. By
considering the idea of taking the derivative, we find that the complexity of a finite graph can
be expressed as the partial derivative of the generalized characteristic polynomial FG(λ, µ)
evaluated at (0, 1).
Theorem 2.1. Let FG(λ, µ) = det(λI − (A(G)− µD(G))) be the generalized characteristic
polynomial of a graph G. Then the number of spanning trees in G, κ(G), is
|(0,1),
where εG is the number of edges of G.
Proof. Let Bλ,µ = λI − (A(G) − µD(G)) = ((bλ,µ)ij) and let B
λ,µ = ((bλ,µ)
ij) denote the
matrix Bλ,µ with each entry of k-th row replace the corresponding partial derivative with
respect to µ. Then
(det Bλ,µ) =
sgn(σ)
((bλ,µ)iσ(i))
(bλ,µ)
iσ(i)) =
(det Bkλ,µ).
Since (b0,1)
ij = d
i δij + aij(δkj − 1) = diδij − aij + aijδki,
|(0,1) =
det (B0,1 + aij(δki)).
Let (Mk)ij = aijδki and let (C0,1)ij be the cofactor of bij in B0,1. Then
det (B0,1 +M
(B0,1 +M
k)kj(−1)
k+j(C0,1)kj = dk (C0,1)kk.
Since det B0,1 = 0, (C0,1)ij = κ(G) for all i and j [3]. Hence,
|(0,1) =
dk (C0,1)kk = κ(G)
dk = 2 εGκ(G).
Thus,
κ(G) =
|(0,1).
3. Generalized characteristic polynomials of graph bundles
Let G be a connected graph and let ~G be the digraph obtained from G by replacing each
edge of G with a pair of oppositely directed edges. The set of directed edges of ~G is denoted
by E( ~G). By e−1, we mean the reverse edge to an edge e ∈ E( ~G). We denote the directed
edge e of ~G by uv if the initial and the terminal vertices of e are u and v, respectively.
For a finite group Γ, a Γ-voltage assignment of G is a function φ : E( ~G) → Γ such that
φ(e−1) = φ(e)−1 for all e ∈ E( ~G). We denote the set of all Γ-voltage assignments of G by
C1(G; Γ).
4 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
Let F be another graph and let φ ∈ C1(G; Aut(F )). Now, we construct a graph G×φ F
with the vertex set V (G ×φ F ) = V (G) × V (F ), and two vertices (u1, v1) and (u2, v2) are
adjacent in G ×φ F if either u1u2 ∈ E( ~G) and v2 = v
φ(u1u2)
1 = v1φ(u1u2) or u1 = u2 and
v1v2 ∈ E(F ). We call G ×
φ F the F -bundle over G associated with φ (or, simply a graph
bundle) and the first coordinate projection induces the bundle projection pφ : G ×φ F →
G. The graphs G and F are called the base and the fibre of the graph bundle G ×φ F ,
respectively. Note that the map pφ maps vertices to vertices, but the image of an edge can
be either an edge or a vertex. If F = Kn, the complement of the complete graph Kn of n
vertices, then an F -bundle over G is just an n-fold graph covering over G. If φ(e) is the
identity of Aut(F ) for all e ∈ E( ~G), then G ×φ F is just the Cartesian product of G and
F , a detail can be found in [10].
Let φ be an Aut(F )-voltage assignment of G. For each γ ∈ Aut(F ), let ~G(φ,γ) denote
the spanning subgraph of the digraph ~G whose directed edge set is φ−1(γ). Thus the
digraph ~G is the edge-disjoint union of spanning subgraphs ~G(φ,γ), γ ∈ Aut(F ). Let V (G) =
{u1, u2, . . . , uνG} and V (F ) = {v1, v2, . . . , vνF }. We define an order relation ≤ on V (G×
as follows: for (ui, vk), (uj, vℓ) ∈ V (G ×
φ F ), (ui, vk) ≤ (uj, vℓ) if and only if either k < ℓ
or k = ℓ and i ≤ j. Let P (γ) denote the νF × νF permutation matrix associated with
γ ∈ Aut(F ) corresponding to the action of Aut(F ) on V (F ), i.e., its (i, j)-entry P (γ)ij = 1
if γ(vi) = vj and P (γ)ij = 0 otherwise. Then for any γ, δ ∈ Aut(F ), P (δγ) = P (δ)P (γ).
Kwak and Lee expressed the adjacency matrix A(G ×φ F ) of a graph bundle G ×φ F as
follows.
Theorem 3.1 ( [10]). Let G and F be graphs and let φ be an Aut(F )-voltage assignment
of G. Then the adjacent matrix of the F -bundle G×φ F is
A(G×φ F ) =
γ∈Aut(F )
P (γ)⊗A( ~G(φ,γ))
 + A(F )⊗ IνG ,
where P (γ) is the νF × νF permutation matrix associated with γ ∈ Aut(F ) corresponding to
the action of Aut(F ) on V (F ), and IνG is the identity matrix of order νG.
For any finite group Γ, a representation ρ of a group Γ over the complex numbers is a
group homomorphism from Γ to the general linear group GL(r,C) of invertible r×r matrices
over C. The number r is called the degree of the representation ρ [18]. Suppose that Γ ≤ Sn
is a permutation group on Ω. It is clear that P : Γ → GL(r,C) defined by γ → P (γ), where
P (γ) is the permutation matrix associated with γ ∈ Γ corresponding to the action of Γ on
Ω, is a representation of Γ. It is called the permutation representation. Let ρ1 = 1, ρ2, . . . , ρℓ
be the irreducible representations of Γ and let fi be the degree of ρi for each 1 ≤ i ≤ ℓ,
where f1 = 1 and
i=1 f
i = |Γ|. It is well-known that the permutation representation P
can be decomposed as the direct sum of irreducible representations : ρ = ⊕ℓi=1miρi [18]. In
other words, there exists an unitary matrix M of order |Γ| such that
M−1P (γ)M =
(Imi ⊗ ρi(γ)) (2)
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 5
for any γ ∈ Γ, where mi ≥ 0 is the multiplicity of the irreducible representation ρi in
the permutation representation P and
i=1mifi = νF . Notice that m1 ≥ 1 because it
represents the number of orbits under the action of the group Γ.
It is not hard to show that
(M ⊗ IνG)
−1A(G×φ F )(M ⊗ IνG) =
Imi ⊗ ρi(γ)⊗ A(
~G(φ,γ))
+ A(F )⊗ IνG .
For any vertex (ui, vk) ∈ V (G ×
φ F ), its degree is dGi + d
k , where d
i = degG(ui) and
dFk = degF (vk). Then, by our construction of D(G×
φ F ), the diagonal matrix D(G×φ F )
is equal to IνF ⊗D(G) +D(F )⊗ IνG and thus
(M ⊗ IνG)
−1D(G×φ F )(M ⊗ IνG) = IνF ⊗D(G) +D(F )⊗ IνG .
Therefore, the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µD(G)
+ (A(F )− µD(F ))⊗ IνG.
By summarizing these, we obtain the following theorem.
Theorem 3.2. Let G and F be two connected graphs and let φ be an Aut(F )-voltage
assignment of G. Let Γ be the subgroup of the symmetric group Sn. Furthermore, let ρ1 =
1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ, respectively.
Then the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µD(G)
+ (A(F )− µD(F ))⊗ IνG,
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
A graph F is called a Schreier graph if there exists a subset S of SνF such that S
−1 = S
and the adjacency matrix A(F ) of F is
s∈S P (s). We call such an S the connecting set
of the Schreier graph F . Notice that a Schreier graph with connecting set S is a regular
graph of degree |S| and most regular graphs are Schreier graphs [7, Section 2.3]. The
definition of the Schreier graph here is different that of original one. But, they are basically
identical [7, Section 2.4]. Clearly, every Cayley graph is a Schreier graph.
Theorem 3.3. Let G be a connected graph and let F be a Schreier graph with connecting
set S. Let φ : E( ~G) → Aut(F ) be a permutation voltage assignment. Let Γ be the subgroup
of the symmetric group SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Furthermore,
let ρ1 = 1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ,
respectively. Then the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
γ∈Aut(F )
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µ(D(G) + |S|IνG) +
ρi(s)
⊗ IνG
6 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
Proof. Let F be a Schreier graph with a connecting set S. Then the adjacency matrix of
F is A(F ) =
s∈S P (s). Hence, for any voltage assignment φ : E(
~G) → Aut(F ), one can
see that
A(G×φ F ) =
γ∈Aut(F )
P (γ)⊗ A( ~G(φ,γ))
P (s)⊗ IνG.
Let Γ be the subgroup of SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Since F is a regular
graph of degree |S|, one can see that
D(G×φ F ) = IνF ⊗ (D(G) + |S|IνG).
Now, one can have that the matrix A(G×φ F )− µD(G×φ F ) is similar to
Imi ⊗
γ∈Aut(F )
ρi(γ)⊗ A( ~G(φ,γ))− Ifi ⊗ µ(D(G) + |S|IνG) +
ρi(s)
⊗ IνG
It is easy to see that the following theorem follows immediately from Theorem 3.3.
Theorem 3.4. Let G be a connected graph and let F be a Schreier graph with connecting
set S. Let φ : E( ~G) → Aut(F ) be a permutation voltage assignment. Let Γ be the subgroup
of the symmetric group SνF generated by {φ(e), s : e ∈ E(
~G), s ∈ S}. Furthermore,
let ρ1 = 1, ρ2, . . . , ρℓ be the irreducible representations of Γ having degree f1, f2, . . . , fℓ,
respectively. Then the characteristic polynomial FG×φF (λ, µ) of a graph bundle G×
φ F is
Ifi ⊗ [(λ+ µ|S|)IνG + µD(G)] −
γ∈Aut(F )
ρi(γ)⊗A( ~G(φ,γ))−
ρi(s)
⊗ IνG
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = νF . �
Let F = Kn be the trivial graph on n vertices. Then any Aut(Kn)-voltage assignment is
just a permutation voltage assignment defined in [7], and G ×φ Kn = G
φ is just an n-fold
covering graph of G. In this case, it may not be a regular covering. Now, the following
comes from Theorem 3.2.
Corollary 3.5. Let G be a connected graph and let F = Kn. The characteristic polynomial
FGφ(λ, µ) of the connected covering G
φ of a graph G derived from a permutation voltage
assignment φ : E( ~G) → Sn is
FG(λ, µ)×
Ifi ⊗ [(λ+ r)IνG + µD(G)]−
ρi(γ)⊗A( ~G(φ,γ))−
ρi(s)
⊗ IνG
where mi ≥ 0 is the multiplicity of the irreducible representation ρi in the permutation
representation P and
i=1mifi = n. �
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 7
Next, we consider the characteristic polynomial depending on two variable of graph bun-
dles G×φ F where the images of φ lie in an abelian subgroup Γ of Aut(F ) and the fiber F
is r-regular. In this case, for any γ1, γ2 ∈ Γ, the permutation matrices P (γ1) and P (γ2) are
commutative and DF = rIνF .
It is well-known (see [3]) that every permutation matrix P (γ) commutes with the adja-
cency matrix A(F ) of F for all γ ∈ Aut(F ). Since the matrices P (γ), γ ∈ Γ, and A(F ) are
all diagonalizable and commute with each other, they can be diagonalized simultaneously.
i.e., there exists an invertible matrix MΓ such that M
Γ P (γ)MΓ and M
Γ A(F )MΓ are di-
agonal matrices for all γ ∈ Γ. Let λ(γ,1), . . . , λ(γ,νF ) be the eigenvalues of the permutation
matrix P (γ) and let λ(F,1), . . . , λ(F,νF ) be the eigenvalues of the adjacency matrix A(F ).
M−1Γ P (γ)MΓ =
λ(γ,1) 0
. . .
0 λ(γ,νF )
 and M−1Γ A(F )MΓ =
λ(F,1) 0
. . .
0 λ(F,νF )
Using these similarities, we find that
(MΓ ⊗ IνG)
P (γ)⊗A( ~G(φ,γ)) + A(F )⊗ IνG
(MΓ ⊗ IνG)
λ(γ,i)A( ~G(φ,γ)) + λ(F,i)IνG
Recall that
(M ⊗ IνG)
−1D(G×φ F )(M ⊗ IνG)
= IνF ⊗D(G) + rIνF ⊗ IνG =
(D(G) + rIνG).
By summarizing these facts, we find the following theorem.
Theorem 3.6. Let G be a connected graph and let F be a connected regular graph of degree
r. If the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of Aut(F ), then the matrix
A(G×φ F )− µD(G×φ F ) is similar to
(λ(F,i) − rµ)IνG +
λ(γ,i)A( ~G(φ,γ))− µD(G)
Notice that the Cartesian product G × F of two graphs G and F is a F -bundle over
G associated with the trivial voltage assignment φ, i.e., φ(e) = 1 for all e ∈ E( ~G) and
A(G) = A( ~G). The following corollary comes from this observation.
Corollary 3.7. For any connected graph G and a connected r-regular graph F , the matrix
A(G× F )− µD(G× F ) of the cartesian product G× F is similar to
8 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
(λ(F,i) − rµ)IνG+ (A(G)−µD(G))
In particular, if G is a regular graph of degree dG, then the matrix A(G× F )− µD(G× F )
of the cartesian product G× F is
λ(F,i) + λ(G,j) − (r + d)µ
where λ(G,j) (1 ≤ j ≤ νG) and λ(F,i) (1 ≤ i ≤ νF ) are the eigenvalues of G and F ,
respectively. �
Now, we consider the case the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of
Aut(F ). A vertex-and-edge weighted digraph is a pair Dω = (D,ω), where D is a digraph
and ω : V (D)
E(D) → C is a function. We call ω the vertex-and-edge weight function on
D. Moreover, if ω(e−1) = ω(e), the complex conjugate of ω(e), for each edge e ∈ E(D), we
say that ω is symmetric. Given any vertex-and-edge weighted digraph Dω, the adjacency
matrix A(Dω) = (aij) of Dω is a square matrix of order | V (D) | defined by
aij =
e∈E({vi},{vj})
ω(e),
and the degree matrix DDω is the diagonal matrix whose (i, i)-th entry is ω(vi). We define
FDω(λ, µ) = det (λI − (A(Dω)− µDDω)) .
For any Γ-voltage assignment φ of G, let ωi(φ) : V ( ~G)
E( ~G) → C be the function defined
ωi(φ)(v) = degG(v), ωi(φ)(e) = λ(φ(e),i)
for e ∈ E( ~G) and v ∈ V ( ~G) where i = 1, 2, . . . , νF . Using Theorem 3.6, we have the
following theorem.
Theorem 3.8. Let G be a connected graph and let F be a connected regular graph of degree
r. If the images of φ ∈ C1(G; Aut(F )) lie in an abelian subgroup of Aut(F ), then the
characteristic polynomial FG×φF (λ, µ) of a graph bundle G×
φ F is
F ~Gωi(φ)
(λ+ rµ− λ(F,i), µ).
Now, the following corollary follows immediately from Corollary 3.7.
Corollary 3.9. For any connected graph G and a connected r-regular graph F , the char-
acteristic polynomial FG×F (λ, µ) of the cartesian product G× F is
FG(λ+ rµ− λ(F,i), µ).
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 9
In particular, if G is a regular graph of degree dG, then the characteristic polynomial
FG×F (λ, µ) of the cartesian product G× F is
λ+ (r + d)µ− λ(G,j) − λ(F,i)
where λ(G,j) (1 ≤ j ≤ νG) and λ(F,i) (1 ≤ i ≤ νF ) are the eigenvalues of G and F ,
respectively. �
4. Generalized characteristic polynomial of K1,m ×Kn
In this section, we find the generalized characteristic polynomial of K1,m ×Kn and find
the number of spanning trees of K1,m ×Kn. As we mentioned in introduction, K1,m ×Kn
is a typical model for networks with hubs thus, we will count its spanning trees. Since Kn
features many nice structures, we discuss the generalized characteristic polynomial of graph
bundles with a fiber, Cayley graph.
Let A be a finite group with identity idA and let S be a set of generators for A with
the properties that S = S−1 and idA 6∈ S, where S
−1 = {x−1 | x ∈ Ω}. The Cayley graph
Cay(A, S) is a simple graph whose vertex-set and edge-set are defined as follows:
V (Cay(A, S)) = A and E(Cay(A, S)) = {{g, h} | g−1h ∈ S}.
From now on, we assume that A is an abelian group of order n. Let G be a graph and
let φ : E( ~G) → A be an A-voltage assignment. Notice that the left action A on the vertex
set A of Cay(A, S) gives a group homomorphism from A to Aut(Cay(A, S)). Let P be the
permutation representation of A corresponding to the action. Then the map φ̃ : E( ~G) →
Aut(Cay(A, S)) defined by φ̃(e) = P (φ(e)) for any e ∈ E( ~G) is an Aut(Cay(A, S))-voltage
assignment. We also denote it φ. Notice that every irreducible representation of an abelian
group is linear. For convenience, let χ1 be the principal character of A and χ2, . . . , χn be
the other n− 1 irreducible characters of A. Now, by Theorem 3.3, we have that the matrix
A(G×φ Cay(A, S))− µD(G×φ Cay(A, S)) is similar to
|S|(1− µ))IνG +
A( ~G)− µD(G)
(χi(S)− |S|µ) IνG +
χi(γ)A( ~G(φ,γ))− µD(G)
where χi(S) =
χi(s) for each i = 2, 3, . . . , n. By Theorem 3.8, we have that the
characteristic polynomial FG×φCay(A,S)(λ, µ) of a graph bundle G×
φ Cay(A, S) is
FG(λ+ |S|(µ− 1), µ)×
F ~Gωi(φ)
(λ+ |S|µ− χi(S), µ),
where ωi(φ) : V ( ~G)
E( ~G) → C be the function defined by
ωi(φ)(v) = degG(v), ωi(φ)(e) = χi(φ(e))
10 DONGSEOK KIM, HYE KYUNG KIM, AND JAEUN LEE
for e ∈ E( ~G) and v ∈ V ( ~G) where i = 2, 3, . . . , n. Let Kn be the complete graph on n
vertices. Then Kn is isomorphic to Cay(A,A− {idA}) for any group A of order n. Since
χ1(A− {idA}) = n− 1 and χi(A− {idA}) = −1 for each i = 2, 3, . . . , n, we have
FG×φKn(λ, µ) = FG(λ+ (n− 1)(µ− 1), µ)×
F ~Gωi(φ)
(λ+ (n− 1)µ+ 1, µ).
Moreover over if φ is the trivial voltage assignment, then
FG×Kn(λ, µ) = FG(λ+ (n− 1)(µ− 1), µ)× FG(λ+ (n− 1)µ+ 1, µ)
Let G be the complete bipartite graph K1,m which also called a star graph. Notice that
K1,m is a tree and hence every graph bundle K1,m ×
φ F is isomorphic to the cartesian
product K1,m × F of K1,m and F . It is known [9] that for any natural numbers s and t
FKs,t(λ, µ) = (λ+ tµ)
s−1(λ+ sµ)t−1 [(λ+ sµ)(λ+ tµ)− st]
and hence FK1,m(λ, µ) = (λ+ µ)
m−1 [(λ+ µ)(λ+mµ)−m]. Now, we can see that
FK1,m×φKn(λ, µ)
= FK1,m(λ+ (n− 1)(µ− 1), µ)× FK1,m(λ+ (n− 1)µ+ 1, µ)
= [λ+ nµ− (n− 1)]m−1 {[λ + nµ− (n− 1)][λ+ (m+ n− 1)µ− (n− 1)]−m}
×[λ + nµ+ 1](m−1)(n−1) {[λ+ nµ+ 1][λ+ (m+ n− 1)µ+ 1]−m}
Now, by applying Theorem 2.1, we have that the number of spanning trees of K1,m ×Kn
κ(K1,m ×Kn) = n
n−2(m+ n+ 1)n+1(n+ 1)(m−1)(n−1).
References
[1] L. Bartholdi, Counting pathes in graphs, Enseign. Math., 45 (1999), 83–131.
[2] H. Bass, The Ihara.Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717–797.
[3] N. Biggs, Algebraic Graph Theory, 2nd ed Cambridge University Press, London, 1993.
[4] R. Brualdi and H. Ryser, Combinatorial matrix theory, Cambrige Univ. Press, Cambridge, 1991.
[5] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, NewYork, 1979.
[6] Y. Chae, J. H. Kwak, and J. Lee, Characteristic polynomials of some graph bundles, J. Korean Math.
Soc. 30 (1993), 229–249.
[7] J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, New York 1987.
[8] Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math.
Soc. Japan 18 (1966), 219–235.
[9] H. K. Kim and J. Lee, A generalized characteristic polynomial of a graph having a semifree action,
Discrete Mathematics, to appear.
[10] J. H. Kwak and J. Lee, Characteristic polynomials of some graph bundles II, Linear and Multilinear
Algebra 32 (1992), 61–73.
[11] J. H. Kwak, J. Lee, M. Y. Sohn, Bartholdi zeta functions of graph bundles having regular fibers ,
European Journal of Combinatories 26 (2005), 593–605.
[12] R. Lipton, N. Vishnoi and Z. Zalcstein, A Generalization of the Characteristic Polynomial of a Graph,
CC Technical Report; GIT-CC-03-51, http://citeseer.ist.psu.edu/642697.html
[13] H. Mizuno and I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory
Ser. B, 89 (2003), 17–26.
http://citeseer.ist.psu.edu/642697.html
GENERALIZED CHARACTERISTIC POLYNOMIALS OF GRAPH BUNDLES 11
[14] H. Mizuno and I. Sato, Zeta functions of graph coverings, J. Combin. Theory Ser. B, 80 (2000),
247–257.
[15] H. Mizuno and I. Sato, Bartholdi zeta functions of graph coverings, J. Combin. Theory Ser. B, 89
(2003), 27–41.
[16] S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B, 74 (1998), 408–410.
[17] C. Oliveira, N. Maia de Abreu and S. Jurkiewicz, The characteristic polynomial of the Laplacian of
graphs in (a, b)-linear classes, Linear Algebra and its Applications, 356(1) (2002), 113–121.
[18] J.-P. Serre, Linear Representations of Finite Groups, Springer-Verlag, New York, 1977.
[19] H. Stark, A. Terras, Zeta functions of finite graphs and coverings, Adv. Math. 121 (1996), 126–165.
Department of Mathematics, Kyungpook National University, Taegu, 702-201 Korea
E-mail address : dongseok@knu.ac.kr
Mathematics, Catholic University of Taegu, Kyongsan, 712-702 Korea
E-mail address : hkkim@cu.ac.kr
Department of Mathematics, Yeungnam University, Kyongsan, 712-749, Korea
E-mail address : julee@yu.ac.kr
	1. Introduction
	2. Generalized characteristic polynomials and complexity
	3. Generalized characteristic polynomials of graph bundles
	4. Generalized characteristic polynomial of K1,mKn
	References
