In this paper, we consider an extended Kazakov-Migdal model defined on an
arbitrary graph. The partition function of the model, which is expressed as the
summation of all Wilson loops on the graph, turns out to be represented by the
Bartholdi zeta function weighted by unitary matrices on the edges of the graph.
The partition function on the cycle graph at finite $N$ is expressed by the
generating function of the generalized Catalan numbers. The partition function
on an arbitrary graph can be exactly evaluated at large $N$ which is expressed
as an infinite product of a kind of deformed Ihara zeta function. The non-zero
area Wilson loops do not contribute to the leading part of the $1/N$-expansion
of the free energy but to the next leading. The semi-circle distribution of the
eigenvalues of the scalar fields is still an exact solution of the model at
large $N$ on an arbitrary regular graph, but it reflects only zero-area Wilson
loops.
