ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 223-235 Isospectral genus two graphs are isomorphic Alexander Mednykh , Ilya Mednykh Sobolev Institute of Mathematics, 630090, Novosibirsk, Russia Novosibirsk State University, 630090, Novosibirsk, Russia Siberian Federal University, 660041, Krasnoyarsk, Russia Received 10 March 2013, accepted 24 July 2015, published online 3 October 2015 By a graph we mean a finite connected multigraph without bridges. The genus of a graph is the dimension of its homology group. Two graphs are isospectral is they share the same Laplacian spectrum. We prove that two genus two graphs are isospectral if and only if they are isomorphic. Also, we present two isospectral bridgeless genus three graphs that are not isomorphic. The paper is motivated by the following open problem posed by Peter Buser: are isospectral Riemann surfaces of genus two isometric? Keywords: Graph, Laplacian spectrum, isospectral graphs, Laplacian polynomial, spanning tree. Math. Subj. Class.: 05C50, 15A18, 58J53 1 Introduction Over the last decade, a few discrete versions of the theory of Riemann surfaces were created ([1, 18, 2, 8, 11]). In these theories, the role of Riemann surfaces is played by graphs. The genus of a graph is the dimension of its homology group. Under these assumptions, the theory of Jacobi manifolds is constructed and analogues of the Riemann-Hurwitz and Riemann-Roch theorems were proved. Counterparts of many other theorems from the classical theory of Riemann surfaces were derived in the discrete case ([9, 10, 16]). Since the classical paper by Mark Kac [14], the question of what geometric properties of a manifold are determined by its Laplace operator has inspired many intriguing results. One class of manifolds whose spectral theory has been studied with many beautiful results is the class of compact Riemann surfaces with the canonical constant curvature metric. Wolpert [19] showed that a generic Riemann surface is determined by its Laplace spectrum. Nevertheless, pairs of isospectral non-isometric Riemann surfaces in every genus > 4 are known. See papers by Buser [7], Brooks and Tse [5], and others. There are also examples of E-mail addresses: smedn@mail.ru (Alexander Mednykh), ilyamednykh@mail.ru (Ilya Mednykh) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 224 Ars Math. Contemp. 10 (2016) 393-410 isospectral non-isometric surfaces of genus two and three with variable curvature ([5, 3]). At the same time, isospectral genus one Riemann surfaces (flat tori) are isometric [4]. Similar results are also known for graphs ([12, 13]). Peter Buser [6] posed an interesting problem: are two isospectral Riemann surfaces of genus two isometric? Up to our knowledge the problem is still open but, quite likely, can be solved positively. The aim of this paper is to give a positive solution of an analogous problem for bridgeless graphs of genus two (Theorem 3.1). Also, we show that there are two isospectral bridgeless graphs of genus three that are not isomorphic (Figure 5). Because of the intrinsic link between Riemann surfaces and graphs we hope that our result will be helpful to make a progress in solution of the Buser problem. 2 Preliminary results 2.1 Laplacian matrix and Laplacian spectrum The Laplacian matrix of a graph and its eigenvalues can be used in several areas of mathematical research and have a physical interpretation in various physical and chemical theories. The related adjacency matrix of a graph and its eigenvalues were much more investigated in the past than the Laplacian matrix. At the same time, the Laplacian spectrum is much more natural and more important than the adjacency matrix spectrum because of it numerous application in mathematical physics, chemistry and financial mathematics. Graphs in this paper are finite and undirected, but they may have loops and multiple edges. Denote by V(G) and E(G), respectively, the number of vertices and edges of a graph G. Following [2] we denote by g(G) = E(G) — V(G) + 1 the genus of G. This is the dimension of the first homology group of G. In graph theory, the term "genus" is traditionally used for a different concept, namely, the smallest genus of any surface in which the graph can be embedded, and the integer g = g(G) is called the cyclomatic or the Betti number of G. We call g the genus of G in order to highlight the analogy with Riemann surfaces. A bridge is an edge of a graph G whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless if it contains no bridges. Let G be a graph. Denote by V(G) and E(G) the set of vertices and edges of a graph G respectively. For each u, v e V(G), we set auv to be equal to the number of edges between u and v. The matrix A = A(G) = [auv]u,vey(G), is called the adjacency matrix of the graph G. Let d(v) denote the valency of v e V(G), d(v) = J2u auv, and let D = D(G) be the diagonal matrix indexed by V(G) and with dvv = d(v). The matrix L = L(G) = D(G) — A(G) is called the Laplacian matrix of G. It should be noted that loops have no influence on L(G). Throughout the paper we shall denote by ^(G,x) the characteristic polynomial of L(G). For brevity, we will call ^(G, x) the Laplacian polynomial of G. Its roots will be called the Laplacian eigenvalues (or sometimes just eigenvalues) of G. They will be denoted by ^i(G) < ^2(G) < ... < ^n(G), (n = V(G)), always enumerated in increasing order and repeated according to their multiplicity. Recall [17] that for connected graph G we always have ^1(G) = 0 and ^2(G) > 0. Two graphs G and H are called Laplacian isospectral (or isospectral) if their Laplacian polynomials coincide: ^(G,x) = p(H,x). The matrix L(G) is sometimes called the Kirchhoff matrix of G due to its role in the A. Mednykh and I. Mednykh: Isospectral genus two graphs are isomorphic 225 well-known Matrix-Tree Theorem which is usually attributed to Kirchhoff. A generalization of the Matrix-Tree-Theorem was obtained in 1967 by A. K. Kel'mans who gave a combinatorial interpretation to all the coefficients of ^(X, x) in terms of the numbers of certain subforests of a graph X; see [15] and [17] for references and history of question. We present the result by Kel'mans in the following form. Theorem2.1. [15]If^(X,x) = xn-cix"-1 +... + (-1)icixn-i +... + (-1)n-1cn-1x then ci = £ T (Xs), SCV, |S|=n-i where T (H) is the number of spanning trees of H, and XS is obtained from X by identifying all points of S to a single point. 2.2 Theta graphs Let u and v are two (not necessary distinct) vertices. Denote by ©(k, l, m) the graph consisting of three internally disjoint paths joining u to v with lengths k, l, m > 0 (see Fig. 1). We set <7i = 0, then ©(k, l, m) is a graph of genus two. In this case at least two of numbers {k, l, m} are positive. (ii) If 01 > 0,02 = 0, then ©(k, l, m) is a graph of genus one. Then exactly one of numbers {k, l, m} is positive and the other two are zero. Moreover, ©(k, l, m) = Ck+i+m is a cyclic graph with k + l + m edges. 226 Ars Math. Contemp. 10 (2016) 393-410 (iii) If <7i = 0, then k = 1 = m = 0 and ©(k, 1, m) is a graph of genus zero. More precisely, ©(k, 1, m) = ©(0,0,0) consists of one vertex. Lemma 2.2. Let G be an arbitrary bridgeless graph of genus two. Then G is isomorphic to ©(k, 1, m) for some k, 1, m with ct2 = k 1 + 1m + km> 0. Proof. Since the graph G is bridgeless it has no vertices of valency one. Denote by H the graph obtained from G by deleting of all vertices of valency two. Suppose that H has V vertices of valences ni, n2,..., nv and E edges. Since the valency of each vertex of H is at least three we have n > 3, i = 1,2,..., V. Note that deleting of a vertex of valency two decreases the number of vertices and the number of edges of a graph by one. So, it does not affect the genus and H is still a graph of genus two. Thus g(H) = 1 - V + E = 2 and E = V + 1. Counting the sum of valences of H through vertices and through edges we obtain ni + n2 + ... + nv = 2E. Hence 3V < n1 + n2 + ... + nv = 2E = 2V + 2, or V < 2. If V =1 then n1 =4 and H is the figure eight graph consisting of one vertex and two loops. Putting back the vertices of valency two on the graph H we obtain the graph G isomorphic to ©(k, 1,0) for some positive k and 1. In particular, a2 = k 1 > 0. If V = 2 then n1 = n2 =3 and H is the theta graph consisting of two vertices and three edges. The graph G is obtained from H by adding the vertices of valency two. Hence, G is isomorphic to ©(k, 1, m) for some positive k, 1, m. □ 3 Main results 3.1 The main theorem and lemmas The main result of the paper is the following theorem. Theorem 3.1. Two genus two bridgeless graphs are Laplacian isospectral if and only if they are isomorphic. The proof of the theorem is based on the following three lemmas. Lemma 3.2. Let G = ©(k, 1, m) be a theta graph and let ^(G, x) = xn — c1xn-i + ... + ( — 1)n-1cn-1x be its Laplacian polynomial. Then n = k + 1 + m — 1, c1 = 2(k + 1 + m) and cn-1 = (k 1 + 1m + k m)(k + 1 + m — 1). Proof. The number of vertices, edges and spanning trees of graph G are given by V(G) = k + 1 + m — 1, E(G) = k + 1 + m, T(G) = k 1 + 1m + km. Then by ([15], formulas 2.15 and 2.16) we have n = V(G) = k + 1 + m — 1, c1 = 2E(G) = 2(k +1 + m) and cn-1 = V(G) • T(G) = (k1 + 1m + km)(k +1 + m — 1). □ A. Mednykh and I. Mednykh: Isospectral genus two graphs are isomorphic 227 Lemma 3.3. Let G = Q(k, l, m) be a theta graph and let p>(G, x) = xn — c1xn 1 + ... + ( —1)n-1cn-1x be its Laplacianpolynomial. Then Cn-2 = A((J1, (J2) + B(ai, 02)03 where A(s,t) = (4t — 3st — 2s2t + s3t + 4t2 — st2)/12, B(s,t) = (3 — 4s + s2 — 3t)/12, 01 = k + l + m, 02 = kl + l m + km, and (J3 = klm. Proof. By Theorem 2.1 Cn-2 = £ T (Xs ), (3.1) SCV, |S|=2 where XS runs through all graphs obtained from G = Q(k, l, m) by gluing two vertices. There are exactly four types of such graphs G1,G2,G3, and G4 shown in the Fig. 2. We will enumerate the spanning trees of each type separately. Type G1. Glue two 3-valent vertices of graph G. As a result we obtain the graph G1 shown on Fig. 2. The number of spanning trees of this graph is T1 = T(Ck) ■ T(Ci) ■ T (Cm) = klm. Type G2. Glue one 3-valent and one 2-valent vertices of graph G. The graph of type G2 shown in Fig. 2 is obtained by gluing the upper 3-valent of graph G and a 2-valent vertex on the path of G labelled by k. For given i, 1 < i < k — 1 the number of spanning trees for a graph of type G2 is equal to T (Ci) ■ T (Q(k — i,l,m)) = ia2(k — i, l, m). We k-1 set F(k, l, m) = J2 ia2(k — i, l, m). Then the total number of spanning trees for graphs i=1 of type G2 is T2 = 2(F(k, l, m) + F(l, m, k) + F(m, k, l)). The multiple 2 is needed since the graph Q(k, l, m) has two 3-valent vertices. Type G3. Glue two 2-valent vertices of graph G lying on different paths. We choose one of them on the path labelled by k and the second on the path labbeled by l. Fix i, 1 < i < k — 1 and j, 1 < j < l — 1 and consider a graph of type G3 shown in Fig. 2. This is a graph of genus three. To create a spanning tree on this graph we have to delete three edges. There are two different ways to do this. Firstly, we delete edges on three of the four paths labeled by i, j,k — i and l — j. This be done in a3 (i, j,k — i,l — j) ways, where a3(x, y, z, t) = xyz + xyt+xzt+yzt. Secondly, if we delete an edge from the path labeled by m (in m possible ways) then we have to remove one edge from the pair of paths i, j and one edge from the pair k — i,k — j. Then we have m((i + j)(k — i +1 — j)) possibilities to obtain a tree. As the result graph under consideration has G3(i, j, k, l, m) = a3(i, j, k — i, l — j) + m((i + j)(k — i + l — j) spanning trees. We set k-1l-1 J(k, l, m) ^^ G3(i, j, k, l, m). i= 1 j=1 Then the total number of spanning trees for graphs of type G3 is T3 = J(k, l, m) + J(l, m, k) + J(m, k, l). Type G4. Glue two 2-valent vertices lying on the same path of graph G. Choose the path labelled by k. Let us fix i and j such that 1 < i < j < k — 1. Then the number 228 Ars Math. Contemp. 10 (2016) 393-410 of spanning trees for a given graph of type G4 is T(Cj-i)T(0(k + i - j,l,m)) = (j -i)a2(k + i - j,l,m). We set k-2 k-1 H(k, l, m) ^^ ^^ (j - i)&2 (k + i - j, l, m). i=1 j=i+1 As a result, the number of spanning trees of the given type is T4 = H(k, l, m) + H(l, m, k) + H(m, k, l). Putting the obtained formulas in Mathematica 8 by (3.1) we get Cn-2 = Ti + T2 + T3 + T4 = A(ai, <72) + B(ai, 0-2)0-3. k-i I m Figure 2: The graphs obtained from 0(k, l, m) by gluing two vertices Lemma 3.4. Let G = Q(k, l, m) be a theta graph and let p(G, x)= xn - c1xn-1 + ... + (-l)n-1cn-1x be its Laplacian polynomial. Then Cn-3 = C (01,02) + D(<1,02)03 + E (01,02)03, where C(s,t) = (-34t + 21st + 25s2t - 10s3t - 3s4t + s5t - 50t2 + 10st2 + 12s2t2 - 2s3t2 - 16t3 + st3)/360, D(s,t) = (-45 + 50s + 5s2 - 12s3 + 2s4 + 24st - 9s2t + 15t2)/360, E(s,t) = -3(-8 + 3s)/360. A. Mednykh and I. Mednykh: Isospectral genus two graphs are isomorphic 229 Proof. By Theorem 2.1 cn-3 = ^ T (Xs ), (3.2) SCV, |S|=3 where XS runs through all graphs obtained from G = Q(k, l, m) by gluing three vertices. There are six types of such graphs Wi,W2, W3, W4, W5, and W6 shown on the Fig. 3. We examine the spanning trees of each type separately. Type Wi. To create a graph of type Wi we identify two 3-valent vertices of graph G and one 2-valent vertex of G (say on the path labelled by k). The obtained graph is shown in the k-i Fig. 3, has i(k — i)l m spanning trees. Consider the sum Fw (k, l, m) = J2 i(k — i)l m. i= 1 Find the total number of spanning trees for graphs of type Wi by the formula Tw = fw(k, l, m) + Fw (l, m, k) + Fw (m, k, l). Type W2. Glue one 3-valent vertices of graph G and two 2-valent vertices lying on different paths of G (say on the paths labelled by k an l), obtaining a graph in Fig. 3. For given i and j, 1 < i < k — 1, 1 < j < l — 1, the number of spanning trees for graph of k-ii-i type W2 is ija2(k — i,l — j, m). We set Hw(k, l, m) = J2 J2 ija2(k — i,l — j, m). i=ij=i Taking into account that graph Q(k,l, m) has two 3-valent vertices we obtain the following formula the number of spanning trees for graphs of type W2 : T2w = 2(Hw(k, l, m) + Hw(l, m, k) + Hw(m, k, l)). Type W3. Glue one 3-valent vertices and two 2-valent vertices lying on the same path of G. For fixed i and j, 1 < i < j < k — 1, we have i(j — i)a2(k — j, l, m) spanning trees for graph of type W3. Summing over i and j we get k-2 k-i Jw(k, l,m) = ^ ^ i(j — i)a2(k — j, l, m). i=i j=i+i Finally, the number of spanning trees for graphs of type W3 is given by T3? = 2(Jw(k, l, m) + Jw(l, m, k) + Jw(m, k, l)). Type W4. Glue three 2-valent vertices all lying on different paths of G. Fix i, j and s, 1 < i < k — 1, 1 < j < l — 1, 1 < s < m — 1. Then the number of spanning trees for a given graph of type W4 is equal to a2 (i, j, s)a2(k — i,l — j,m — s). Summing over i, j and s we obtain the total number of spanning trees for graphs of type W4 : k-i i-i m-i Tw = a2(i,j, s)°2(k — iJ — j,m — s). i=i j=i s=i Type W5. Glue two 2-valent vertices lying on a path and one 2-valent vertex lying on the other path of G. Denote by G3(i,j,k,l,m) the graph of type G3 shown in Fig. 2. From the proof of previous Lemma we have T (G3(i, j, k, l, m)) = a3(i, j, k — i,l — j) + m((i + 230 Ars Math. Contemp. 10 (2016) 393-410 j)(k — i + l — j)). Fix i, j and s, 1 < i < j < k — 1, 1 < s < l — 1. Then the number of spanning trees for a graph of type W5 in Fig. 3 is equal to T(Cj-i)T(G3(i, s,k + i — j, l, m)) = (j — i)T(G3(i, s,k + i — j, l, m)). Consider the sum k-2 k-1 l-l Kw (k,l, m) = EE E(j — i)T (Gs(i,s,k + i — j, l, m)). i=l j=i+l s = l Then the number of spanning trees for graphs of type W3 is given by Tw = kw (k, l, m) + Kw (l, m, k) + Kw (m, k, l) + Kw(k, m, l) + Kw(l, k, m) + Kw(m, l, k). (3.3) Type W6. Glue three 2-valent vertices on the same path of G. Fixed i,j and s such that 1 < s < i < j < k — 1. Then the number of spanning trees for a given graph of type W6 is equal to T(Ci-a)T(Cj-i)T(G(k — j + s, l, m)) = (i — s)(j — i)a2(k — j + s, l, m). Summing over i, j and s we obtain Lw (k,l,m)= (i — s)(j — i)&2(k — j + s,l,m). l 1 and o' > 1. Then the system of equations (3.4) gives ai = o' and o2 = o2. The theorem will be proved if we show that o3 = o3. We will do this in two steps. First of all, we note that by [13] isospectral graphs with n < 5 vertices are isomorphic. So, we can assume that n = k + l + m - 1 > 5, that is, oi = k + l + m > 6. By Lemma 3, Cn-2 = A(0i,02)+ B(oi, 02)03, (3.5) where A(s,t) = (4t - 3st - 2s2t + s3t + 4t2 - st2)/12 and B(s,t) = (3 - 4s + s2 - 3t)/12. Step 1. B(oi,o2) = 0. Since c^-2 = cn-2,oi = o' ando2 = o2 from (3.5) we obtain B(oi,o2)o3 = B(oi,o2)o3. (3.6) Hence o3 = o3' and the theorem is proved. Step 2. ^(o', o2) = 0. Then by Lemma 3 cn-3 = c (oi,o2) + D(o i ,o2)o3 + E (oi,o2)o|, (3.7) where C(s, t) = (-34t + 21st + 25s2t - 10s3t - 3s4t + s5t - 50t2 + 10st2 + 12s2t2 - 2s3t2 - 16t3 + st3)/360, D(s,t) = (-45 +50s + 5s2 - 12s3 + 2s4 + 24st - 9s2t + 15t2)/360, E (s,t) = -3(-8 + 3s)/360. 232 Ars Math. Contemp. 10 (2016) 393-410 Since = cn-3, a1 = a1 and a2 = a2 from (3-7) we obtain D(CTI,CT2)^3 + E(ai, a2)a?2 = D(ai, a2)a? + E(ai,a2)a|. (3-8) We note that E(a1,a2) = 0 for any integer a1. Then the above equation has two solutions with respect to a?. The first solution is a? = a3 and the second one is , D(a1,a2) a (3 9) a3 = -V - a3. (3-9) E(ai,a2) In the first case the theorem is proved- So we assume that a3 is given by equation (3.9). Recall that B(a1,a2) = 0. Then a2 = (3 — 4a1 + a2)/3 and equation (3.9) can be rewritten in the form a3 = (2(425 " 357a 1 — 144a2 + 27a?) — "^^) " as. (3-10) Since a3 and a3 are integers the number N = 2(425 — 357a 1 — 144a2 + 27a?) — 490 —8 + 3a1 is an integer divisible by 729. Moreover, —8 + 3a1 is a divisor of 490 and the number a2 = (3 — 4a1 + a2)/3 is a positive integer. There are a finite number possibilities of a positive integer a1 to satisfy these three conditions, namely, a1 G {6,19,166}. The case a1 = 6 can be excluded since we suggested that a1 > 6. Another way to exclude a1 = 6 is to check that in this case a? = —3 — as is negative. Consider the remaining cases a1 = 19 and a1 = 166. By (3.10) in these cases we have a? = 348 — a? and a? = 327789 — a? respectively. The respective values of a2 are 96 and 8965. Let a1 = 19. We have the following system of equations to find positive integer parameters k, l, m, a? of the graph G = ©(k, l, m) : k + l + m =19, kl + Im + mk = 96, klm = a?. This system has only one solution {k, l, m} = {3, 4, 12}, a3 = 144. Now we are able to find parameters k3, l3, m3, a3 of the graph G3 = ©(k3, l3, m3). First of all, a3 = 348 — a? = 204. Then we have k3 + l3 + m3 = 19, k3l3 + l3m3 + m3k = 96, k3l3m3 = 204. The latter system has no integer solutions. So the case a1 = 19 is impossible. Let a1 = 166. We have the following system k, l, m, a?. k + l + m = 166, k l + l m + m k = 8965, klm = a?. This system has only one solution {k, l, m} = {39,59,68}, a? = 39 • 59 • 68. Find parameters k3, l3, m3, a3 of the graph G3 = ©(k3, l3, m3). Now, a3 = 327789 — a? = 171321. Then we have k3 + l3 + m3 = 166, k3l3 + l3m3 + m3k3 = 8965, k3l3m3 = 171321. The system has no integer solutions. The case a1 = 166 is also impossible. This completes the proof. □ A. Mednykh and I. Mednykh: Isospectral genus two graphs are isomorphic 233 4 Final remarks 1. The main Theorem 3.1 is not valid for genus two graphs with bridges. Indeed, the following two graphs (see Fig. 4) constructed in [12] are isospectral. They share the Laplacian polynomial —72x + 192x2 - 176x3 + 73x4 - 14x5 + x6. The first of these graphs is bridgeless, while the second one has a bridge. 2. There are isospectral bridgeless graphs of genus three which are not isomorphic (see Fig. 5). These two graphs were constructed in [13].They share the Laplacian polynomial —384x + 1520x2 - 2288x3 + 1715x4 - 708x5 + 164x6 - 20x7 + x8. 3. Any bridgeless graph of genus one is isomorphic to a cyclic graph Cn for some n > 1. If two cyclic graphs Cm and Cn are isospectral then their Laplace polynomials are of the same degree m = n. Hence, the graphs are isomorphic. 234 Ars Math. Contemp. 10 (2016) 393-410 At the same time, there are isospectral unicycle graphs [20]. For example, the two genus one graphs shown on Fig. 6 share the Laplacian polynomial 28x - 146x2 + 250x3 - 194x4 + 75x5 - 14x6 + x7. 4. One can hear the genus of a graph. That is, the genus of a graph G is completely determined by its Laplace spectrum. Indeed, g(G) = 1 - V(G) + E(G). Let p(G,x) = xn-c1xn-1 + ...+(- 1)n-1cn-1x be the Laplacian polynomial of G. By the arguments from the proof of Lemma 3.2 we have n = V(G) and c1 = 2E(G). Thus V(G) and E(G), as well as the genus, are uniquely determined by the Lapla-cian polynomial. It follows from this observation, the previous remark, and the main result of the paper that the bridgeless graphs of genera one and two are recognisable by their Laplacian spectra among all bridgeless graphs. 5. One cannot hear a bridge of a graph. Indeed, the two graphs in Fig. 4 are isospectral. We are not able to recognise the existence of a bridge of the second graph by its spectrum. 5 Acknowledgments The authors are thankful to the following grants for partial support of this investigation: the Russian Foundation for Basic Research (project no. 15-01-07906), the Grant of the Russian Federation Government at Siberian Federal University (grant 14.Y26.31.0006), the Program "Leading Scientific Schools" (project no. NSh-921.2012.1), the Dynasty Foundation and the Project: Mobility - enhancing research, science and education at the Matej Bel University, ITMS code: 26110230082, under the Operational Program Education cofi-nanced by the European Social Fund and by Slovenian-Russian grant (2014-2015). A. Mednykh and I. Mednykh: Isospectral genus two graphs are isomorphic 235 References [1] R. Bacher, P. de la Harpe, and T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France, 125 (1997), 167-198. [2] M. Baker, S. Norine, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Notes, 15 (2009), 2914-2955. [3] D. Barden and Hyunsuk Kang, Isospectral surfaces of genus two and three, Math. Proc. Cambridge Philos. Soc., 153(1) (2012), 99-110. [4] R. Brooks, Constructing Isospectral Manifolds, Amer. Math. Monthly, 95 (9) (1988), 823-839, [5] R. Brooks and R. Tse, Isospectral surfaces of small genus, Nagoya Math. J., 107 (1987), 13-24. [6] P. Buser, Geometry and spectra of compact Riemann surfaces, Progress in Mathematics, 106 Birkhhauser, Boston, MA, 1992. [7] P. Buser, Isospectral Riemann surfaces, Ann. Inst. Fourier, 36 (1986), 167-192. [8] L. Caporaso, Algebraic and tropical curves: comparing their moduli spaces,in: G. Farkas, I. Morrison (eds.), Handbook of Moduli, I, Advance Lectures in Mathematics,XXIV(2011),119-160. [9] L. Caporaso, Gonality of algebraic curves and graphs, in: Algebraic and Complex geometry: in honor of Klaus Hulek's 60th Birthday, Springer Procedings in Mathematics & Statistic 71 (2014), 77-109. [10] S. Corry, Genus bounds for harmonic group actions on finite graphs, Inter. Math. Res. Not., 19 (2011), 4515-4533. [11] S. Corry, Harmonic Galois theory for finite graphs, H. Nakamura, F. Pop, L. Schneps, A. Tam-agawa (eds.), in: Galois-Teichmuller Theory and Arithmetic Geometry, Advanced Studies in Pure Mathematics, 63 (2012), 121-140. [12] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra and its Applications, 373 (2003), 241-272. [13] W. H. Haemers and E. Spence, Enumeration of cospectral graphs, European J. ofCombin. 25(2) (2004), 199-211. [14] M. Kac, Can one hear the shape of a drum?, Amer. Math. Monthly, 73 (4 (part II)) (1966), 1-23. [15] A. K. Kel'mans and V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory, Ser. B, 16(3) (1974), 197-214. [16] I. A. Mednykh, On the Farkas and Accola Theorems for Graphs, Doklady Mathematics, 87(1) (2013), 65-68. [17] B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk (eds.), Graph theory, combinatorics, and applications, Wiley, 2 (1991), 871898. [18] H. Urakawa, A discrete analogue of the harmonic morphism and Green kernel comparison theorems, Glasgow Math. J., 42(3) (2000), 319-334. [19] S. Wolpert, The length spectra as moduli for compact Riemann surfaces, Ann. Math. (2), 109(2) (1979), 323-351. [20] Xiaoling Shen and Yaoping Hou, A class of unicyclic graphs determined by their Laplacian spectrum, Electronic Journal ofLinear Algebra, 23 (2012), 375-386.