Distinguishing graphs by their left and right homomorphism profiles

Distinguishing graphs by their left and right homomorphism profiles Delia Garijo a, Andrew Goodall b, Jaroslav Nešetřil b a Department of Applied Mathematics I, University of Seville, Seville, Spain b Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Prague, Czech Republic abstract We introduce a new property of graphs called ‘q-state Potts unique-ness’ and relate it to chromatic and Tutte uniqueness, and also to ‘chromatic–flow uniqueness’, recently studied by Duan, Wu and Yu. We establish for which edge-weighted graphs H homomor-phism functions from multigraphs G to H are specializations of the Tutte polynomial of G, in particular answering a question of Freed-man, Lovász and Schrijver. We also determine for which edge-weighted graphs H homomorphism functions from multigraphs G to H are specializations of the ‘edge elimination polynomial’ of Averbouch, Godlin and Makowsky and the ‘induced subgraph poly-nomial’ of Tittmann, Averbouch and Makowsky. Unifying the study of these and related problems is the notion of the left and right homomorphism profiles of a graph. 1. Introduction The question of whether a graph is uniquely determined by its characteristic polynomial (spectrum) or by its chromatic polynomial has received much attention. In recent years it has been conjectured that almost all graphs are determined by their chromatic polynomial [6] and that almost all graphs are determined by their characteristic polynomial [35]. On the other hand, for example, all trees have the same chromatic polynomial and almost every tree is cospectral with another tree [32]. Showing that a particular graph is determined by a given polynomial invariant often involves intricate arguments. Some insight may be found by a comparative study of the way in which related polynomial invariants determine graphs up to isomorphism. In this paper, which expands and develops the extended abstract [17], we show how graph homomorphisms might provide a fruitful theoretical basis for such a study. E-mail addresses: [email protected] (D. Garijo), [email protected], [email protected] (A. Goodall), [email protected] (J. Nešetřil). The chromatic polynomial is a specialization of the Tutte polynomial. Bollobás et al. [6] precede their conjecture on the chromatic polynomial by the weaker conjecture that almost all graphs are determined by their Tutte polynomial. Many families of graphs have been shown to be determined by the Tutte polynomial that are not determined by the chromatic polynomial, the first paper devoted to the subject being [11]. Another well-known specialization of the Tutte polynomial is the flow polynomial. The question of whether the flow polynomial determines a graph was only recently considered by Duan et al. [13]. These authors also explore when a graph is determined by its chromatic polynomial and flow polynomial jointly. In Section 3, we use right homomorphism profiles to unify discussion of the question of when a graph is determined by a polynomial graph invariant such as the chromatic polynomial, flow polynomial or Tutte polynomial. Our first main result here is Theorem 11, showing that the ‘colouring uniqueness’ of [19] coincides with Tutte uniqueness. This prompts introducing the idea of ‘q-state Potts uniqueness’, which as far was we know has not yet been studied. In Section 3.3, we establish by example some graph invariants that are not determined by the 2-state Potts partition function and also that ‘2-state Potts uniqueness’ differs from Tutte uniqueness, chromatic–flow uniqueness, chromatic uniqueness, and q-state Potts uniqueness for q≥3. The 2-state Potts partition function is a specialization not only of the Tutte polynomial but also of the ‘Ising polynomial’ of Andrén and Markström [2]: a pair of Tutte equivalent or ‘isomagnetic’ graphs are also 2-state Potts equivalent. In Section 3.4, we find graph invariants that are determined by the partition function of the q-state Potts model and use these to show that all the ‘chromatic–flow unique’ graphs of Duan et al. [13] are also ‘q-state Potts unique’. Section 4of this paper concerns the question of when a homomorphism profile determines a given graph up to isomorphism, first considered by Lovász [26]. The case of left homomorphism profiles by cycles includes the question of graphs determined by their characteristic polynomial (Corollary 27). In this section, we consider the following type of problem for a graph parameter h: find a minimal set of graphs Gfor which the values h(G)are sufficient to determine that his a Tutte–Grothendieck invariant. The answer to this specific question is given by Theorem 53; to reach it we use left homomorphism profiles. Theorem 53 also includes an answer to a question of Freedman et al. [16, Example 3.3]. A similar question1for the trivariate generalization ξ(G;x,y,z)of the Tutte polynomial of Averbouch, Godlin and Makowsky [3] is answered by Theorem 37 in Section 4.3. Likewise, in Section 4.4, we consider the similar question for the recently introduced ‘induced subgraph polynomial’ Q(G;x,y)of Tittmann et al. [33]. In Section 5, we highlight some open problems. 2. Preliminaries 2.1. Homomorphism profiles A homomorphism of a graph Gto a graph His a function f:V(G)→V(H)such that f(u)f(v) ∈ E(H)whenever uv∈E(G). When Gand Hare multigraphs, i.e., they might have parallel edges and loops, a homomorphism of Gto His a pair of functions fV:V(G)→V(H)and fE:E(G)→E(H) with the property that if e∈E(G)has endpoints uand vthen fE(e)has endpoints fV(u)and fV(v). When Gand Hare simple, this corresponds to a homomorphism, as previously defined. In the case of multigraphs the function fEmaps parallel edges (resp., loops) in Gto parallel edges (resp., loops) in H. For a multigraph Gand an edge-weighted graph Hwith symmetric adjacency matrix A(H)=(au,v), we define hom(G,H)=− f:V(G)→V(H)∏ e∈E(G) endpoints iand j af(i),f(j). 1Raised by J. Makowsky at the ‘Graph Limits, Homomorphisms and Structures’ workshop, Hraniční zámeček, Czech Republic, January 2009. When au,v ∈Z≥0indicates the multiplicity of edges joining uand vin a multigraph H, the quantity hom(G,H)is equal to the number of homomorphisms from Gto H. From now on in this paper we shall usually avoid using the longer word multigraph and allow the term graph to include the possibility of loops and parallel edges, unless explicitly stated otherwise by specifying the graph to be simple. On the other hand, in an edge-weighted graph we assume there are no parallel edges (but there are possibly loops of non-zero weight). Definition 1. Let Gbe a family of graphs and Ha family of edge-C-weighted graphs. The right H-profile of G∈Gis the vector (hom(G,H):H∈H). The left G-profile of H∈His the vector (hom(G,H):G∈G). We say that the right H-profile distinguishes a pair of non-isomorphic graphs Gand G′if (hom(G,H):H∈H)= (hom(G′,H):H∈H). A graph Gis determined by its right H-profile if G∼ =G′whenever G′has the same right H-profile as G; in other words, Gis distinguished from other graphs by its right H-profile. Similarly, the left G-profile determines a graph Hif H∼ =H′whenever H′has the same left G-profile as H. As usual, Ck,Pkand Kkdenote the cycle, path and complete graph on kvertices, respectively. The graph P1is an isolated vertex, C1is a loop on one vertex, and C2consists of two parallel edges joining a pair of vertices. Example 2. If G= {P1} ∪ {Ck:k∈Z>0}then the left G-profiles of Hand H′are the same if and only if Hand H′are cospectral. (See Corollary 27.) If H= {Kq:q∈Z>0}then Gand G′have the same right H-profile if and only if Gand G′are chromatically equivalent. 2.2. Tutte–Grothendieck invariants Let G=(V,E)be a graph with k(G)components, rank r(G)= |V| − k(G)and nullity n(G)= |E| − r(G). The graphs resulting by deleting and contracting an edge e∈Eare denoted by G\eand G/e, respectively. An edge eis a bridge in Gif r(G\e)=r(G)−1 and a loop in Gif n(G/e)=n(G)−1. Call an edge ordinary if it is neither a bridge nor a loop of G. Definition 3 ([9]).A function Ffrom (isomorphism classes of) graphs to C[α, β, γ , x,y]is a generalized Tutte–Grothendieck invariant if it satisfies, for each graph G=(V,E)and any edge e∈E, F(G)=     γ|V|E= ∅, xF(G/e)ea bridge, yF(G\e)ea loop, αF(G/e)+βF(G\e)eordinary. (1) For A⊆E, the subgraph (V,A)is obtained from Gby deleting edges not in A. Given G=(V,E), the rank of the spanning subgraph (V,A)is denoted by r(A). A generalized Tutte–Grothendieck invariant is an evaluation of the Tutte polynomial, defined by T(G;x,y)=− A⊆E (x−1)r(E)−r(A)(y−1)|A|−r(A).(2) The coefficients of the Tutte polynomial are non-negative integers (see for example [4,5]), a fact while not evident from its definition in Eq. (2) is more readily seen in its alternative formulation as a Tutte–Grothendieck invariant with α=β=γ=1. Theorem 4 ([9]).If F is a generalized Tutte–Grothendieck invariant satisfying (1) then F(G)=γk(G)αr(G)βn(G)TG;x α,y β. See [5] for how to interpret this evaluation when α=0 or β=0. Definition 5 (See for example [36, Section 4.4]).The q-state Potts partition function P(G)=P(G;q,y) (monochrome polynomial, bad colouring polynomial, coboundary polynomial) of a graph G=(V,E) is defined by P(G;q,y)=− φ:V→[q] y|{ij∈E:φ(i)=φ(j)}|. It is easily verified that the q-state Potts partition function Psatisfies P(G)=     q|V|E= ∅, (y+q−1)P(G/e)ea bridge, yP(G\e)ea loop, (y−1)P(G/e)+P(G\e)eordinary. By Theorem 4, P(G;q,y)=qk(G)(y−1)r(G)TG;y−1+q y−1,y.(3) In particular, the chromatic polynomial P(G;q)is given by P(G;q)=qk(G)(−1)r(G)T(G;1−q,0). 2.3. Homomorphism functions and Tutte–Grothendieck invariants In [19], a local function h(G)is a function defined on graphs Gwith the property that h(G) h(G/e)=αeordinary, a e a bridge, A e a loop, (4) and h(G) h(G\e)=βeordinary, b e a bridge, B e a loop, (5) where α, a,A, β, b,B∈Q\ {0}are constants (i.e., independent of Gand e). Proposition 6. Suppose that h is a local function defined on all graphs G by Eqs. (4) and (5) and which is multiplicative over disjoint unions. Then h(G)=γk(G)αr(G)βn(G)for constants α, β, γ . Proof. In Eqs. (4) and (5), we must have A=B, since h(G)=Ah(G/e)=Bh(G\e)and G/e=G\efor a loop e. Since both h(K3)=αh(C2)=αβh(P2)and h(K3)=βh(P3)=βah(P2), it follows that a=α. Similarly, A=β, since both h(C2)=αh(C1)=αAh(P1)and h(C2)=βh(P2)=βah(P1). Suppose further that his multiplicative over disjoint unions and h(P1)=γfor some non-zero constant γ. Then a=γb, since h(P2)=ah(P1)=bh(P1∪P1)=bh(P1)2. The function h(G)must be determined by the recursion given by Eqs. (4) independently of the order in which the edges eare deleted and contracted from G. Hence a graph parameter h(G)that is multiplicative over disjoint unions is local if and only if the following simplified versions of Eqs. (4) and (5) hold for some constants α, β, γ : h(G) h(G/e)=αenot a loop, βea loop; h(G) h(G\e)=βenot a bridge, α γea bridge. (6) These together say that h(G)=     γ|V|E= ∅, αh(G/e)ea bridge, βh(G\e)ea loop, αh(G/e)=βh(G\e)=δαh(G/e)+(1−δ)βh(G\e)eordinary, where δis arbitrary. By Theorem 4, this yields, for any δ, h(G)=γk(G)(δα)r(G)[(1−δ)β]n(G)TG;1 δ,1 1−δ =γk(G)αr(G)βn(G), with 1 δ−1 1 1−δ−1=1 and T(G;x,y)=(x−1)r(E)y|E|when (x−1)(y−1)=1. This completes the proof.  For fixed H, the function hom(G,H)is multiplicative over disjoint unions, so the graph parameter h(G)T(G;x,y)cannot be a homomorphism number if h(G)is not multiplicative over disjoint unions. By Proposition 6, if h(G)is a local function and h(G)T(G;x,y)is a homomorphism number then h(G)=γk(G)αr(G)βn(G)for some constants α, β, γ . Let Ka,b qdenote the edge-C-weighted complete graph on qvertices with loops attached at each vertex, having weight aon loops and weight bon non-loops. A multigraph can be regarded as an edge-Z≥0-weighted graph with edge weights indicating multiplicities. Theorem 7 ([19]).For every connected graph H, the following statements are equivalent. (i) There exist x,y∈Qand a local function h such that hom(G,H)=h(G)T(G;x,y)for every graph G. (ii) There exist a,b,q∈Z≥0,q≥1, such that H ∼ =Ka,b q. Allowing disconnected graphs Hin Theorem 7, a generalized Tutte–Grothendieck invariant can arise from hom(G,H)only by taking Hequal to the disjoint union of copies of one such connected graph Ka,b q. Remark 1. Compare [16, Example 3.3], where connection matrices are used to deduce that there is an edge-R-weighted graph Hsuch that hom(G,H)=(1−x)k(G)(1−y)|V|T(G;x,y)if and only if (x−1)(y−1)=qfor integers q≥1. (In fact, more is proved in [16], since His also allowed to have positive real weights on its vertices.) This result and Proposition 6 give an alternative proof of Theorem 7. For a minor-closed class of graphs G, we define a function hon graphs to be G-local if it is only required to satisfy Eqs. (4) and (5) for G∈G. By the argument beginning the proof of Proposition 6, if aG-local function his also multiplicative over disjoint unions and Gcontains K3(i.e., some graph with a cycle of length at least three) then hsatisfies the simplified recurrence (6). However, now it is not necessarily the case that h(G)=γk(G)αr(G)βn(G)for constants α, β, γ , since the recurrence (6) need not hold for graphs Goutside the set G. From the proof of Theorem 2.7 in [19], it is straightforward to prove the following result, since the argument of the proof only uses graphs from the given set G. Theorem 8. Let H be a connected graph and G= {Kk,0 1,K0,k 2,Ck,Pk:k∈Z>0}. The following statements are equivalent. (i) There exist x,y∈Qand a G-local function h such that hom(G,H)=h(G)T(G;x,y)for every graph G∈G. (ii) There exist a,b,q∈Z≥0,q≥1, such that H ∼ =Ka,b qand hom(G,H)=h(G)T(G;x,y)for every graph G. In Section 4.5, we prove a generalization of Theorem 8. 3. Right homomorphism profiles and ‘q-state Potts uniqueness’ 3.1. The Tutte polynomial and colouring uniqueness The problem of finding graphs determined by polynomial invariants has been studied for many polynomials (see [30] for a survey). A graph Gis said to be Tutte unique if T(G;x,y)=T(G′;x,y) implies that G∼ =G′, for every other graph G′. Tutte uniqueness has been studied for several families of graphs, such as complete multipartite graphs, wheels and hypercubes (see [11]). The following notion was motivated by the result of Theorem 7 above. Definition 9 ([19]).A finite graph Gis colouring unique if hom(G,Ky,1 q)=hom(G′,Ky,1 q)for all q≥1, y∈Z≥0implies that G∼ =G′for every graph G′. A graph Gis colouring unique if and only if Gis determined by its right {Ky,1 q:q≥1,y∈Z≥0}- profile. Whether a graph is determined by its right {Ky,1 q:q∈Z>0}-profile includes the question of chromatic uniqueness (y=0) and flow uniqueness (y=1−q). Observe that chromatically unique graphs are colouring unique. Similarly, colouring unique graphs are Tutte unique. We now prove that the converse is also true. Lemma 10 ([1, Lemma 2.1]).Let f =f(x1,x2,...,xn)be a polynomial in n variables over an arbitrary field F. Suppose that the degree of f as a polynomial in xiis at most tifor 1≤i≤n, and let Ai⊆F be a set of at least ti+1distinct elements of F. If f (x1,x2,...,xn)=0for all n-tuples (x1,x2,...,xn)∈ A1×A2× · · · × Anthen f is identically zero. Theorem 11. Suppose that G,G′are graphs with max{r(G), r(G′)}<r and max{n(G), n(G′)}<s. Let A,B⊆Cbe sets with |A| = r,|B| = s. Then T(G;x,y)=T(G′;x,y)if and only if T(G;u, v) = T(G′;u, v) for all (u, v) ∈A×B. In particular, G is Tutte unique if and only if G is colouring unique. Proof. If T(G;x,y)=T(G′;x,y)identically then T(G;u, v) =T(G′;u, v) for all (u, v) ∈C×C. Suppose now that T(G;u, v) =T(G′;u, v) for all (u, v) ∈A×B. For all (x,y)∈A×Bwe have the following equality: T(G;x,y)=− (u,v)∈A×B∏ (a,b)∈A×B a=u,b=v x−a u−a y−b v−bT(G;u, v). (7) A similar equality holds with G′in place of G. By Lemma 10, it follows that equality (7) is a polynomial identity. Hence if T(G′;u, v) =T(G;u, v) for all (u, v) ∈A×Bit follows that T(G′;x,y)=T(G;x,y)identically too. For the last part of the theorem, observe that the set y−1+q y−1,y:q≥1,y∈Z≥0contains arbitrarily large rectangles. In order to contain the rectangle A×Bfor given subsets A,B⊆Z≥0\{0,1} with |A| = r,|B| = s, allow qto range over the set {(a−1)(b−1):(a,b)∈A×B}and yto range over B. Suppose that Gis colouring unique, i.e., if T(G′;u, v) =T(G;u, v) for all (u, v) ∈ {(y−q+1 y−1,y): q≥1,y∈Z≥0}then G′∼ =G. By taking r>max{r(G), r(G′)},s>max{n(G), n(G′)}, the equality T(G′;u, v) =T(G;u, v) for all (u, v) ∈A×Bimplies the identity T(G′;x,y)=T(G;x,y). 3.2. The q-state Potts partition function We recall from Definition 5 the q-state Potts partition function, P(G;q,y)=− φ:V(G)→[q] y|{ij∈E(G):φ(i)=φ(j)}|,(8) and that it is the specialization of the Tutte polynomial given in Eq. (3) in Section 2.2. In particular, for y=0 it is equal to the chromatic polynomial P(G;q), and for y=1−qit specializes to the flow polynomial F(G;q). The result of Theorem 11 prompts the question as to which Tutte polynomial invariants of Gare not determined by the right H-profile of Gwhen His a proper subset of {Ky,1 q:q≥1,y∈Z≥0}. The right {K0,1 q:q∈Z>0}-profile of Ggives by interpolation the chromatic polynomial of G, and the right {K1−q,1 q:q∈Z>0}-profile of Ggives the flow polynomial of G. The case where yis variable and q fixed gives a profile determining the q-state Potts partition function of G, since by Eq. (8) we see that hom(G,Ky,1 q)=P(G;q,y). Definition 12. A graph is q-state Potts unique if it is determined up to isomorphism by its right {Ky,1 q:y∈Z≥0}-profile. Our aim in this section is to begin an exploration of which graph invariants are determined by P(G;q,y)(fixed q). In particular, we shall be interested in seeing how q-state Potts uniqueness relates to ‘chromatic–flow uniqueness’ explored by Duan et al. [13]. Fix an arbitrary orientation of G=(V,E). Let δ:ZV q→ZE qdenote the coboundary map (taking the difference between the values at the head and tail of an edge) and ∂:ZE q→ZV qthe boundary map (taking the net flow into a vertex from incoming and outgoing edges). The set im(δ) of Zq-tensions of G has size qr(G)and the set ker(∂) of Zq-flows of G has size qn(G). The weight enumerator of ker(∂) (known also as the boundary polynomial or bad flow polynomial of G) is defined by F(G;q,x)=− f∈ker(∂) x|{e∈E:f(e)=0}|. For a lengthier exposition of the subject of the last paragraph and a full proof of the following lemma, see, for example, [21]. Lemma 13. The q-state Potts partition function of G is given by P(G;q,y)=qk(G)− f∈im(δ) y|{e∈E:f(e)=0}|, and F(G;q,x)=q−|V|(x−1)|E|PG;q,x−1+q x−1 =(x−1)n(G)TG;x,x−1+q x−1. The 2-state Potts partition function is given by P(G;2,y)=2k(G)− cutsetsC y|E|−|C| =2|V|−|E|(y−1)|E|FG;2,y+1 y−1, in which F(G;2,x)=− Eulerian subgraphs C x|E|−|C|. Proof. The first equation uses the 1-to-qk(G)correspondence between Zq-tensions of Gand vertex Zq-colourings of G. The second equation follows by MacWilliams duality and Eq. (3). When q=2, ker(∂) is the subspace of Eulerian subgraphs of G(Z2-flows) and im(δ) the subspace of cutsets of G (Z2-tensions).  3.3. Some 2-state Potts equivalent graphs To begin our discussion of q-state Potts uniqueness, we consider the case q=2, i.e., the partition function of the Ising model P(G;2,y). We return to general qin Section 3.4. A graph is simple if it has no 1-edge or 2-edge cycles, and cosimple if it has no 1-edge or 2-edge cutsets. As observed in [13, Corollary 2.5], whether Gis simple can be detected given both P(G;q)and |E|, but not whether Gis cosimple. Similarly, whether Gis cosimple can be detected by F(G;q)and |E| jointly, but not whether Gis simple. On the other hand, since by Lemma 13 P(G;2,y)records both the number of 1-edge and 2-edge cycles and the number of 1-edge and 2-edge cutsets, the 2-state Potts partition function determines both whether Gis simple or cosimple. (Similarly, in [13], it is shown that the chromatic and flow polynomial when taken together determine whether Gis simple or cosimple.) Fig. 1. Graphs with the same 2-state Potts partition function but different Tutte polynomials. (They also have different chromatic polynomials and different flow polynomials.) One is 2-connected, the other not. Fig. 2. Simple graphs with the same 2-state Potts partition function but different Tutte polynomials. They also have different chromatic polynomials. The graphs in Fig. 1 have the same 2-state Potts partition function. Their q-state Potts model partition functions are respectively (y2+q−1)3and (y+q−1)3+(y3−1)(y3+3(q−1)y+(q−1)(q−2)). These are equal for q∈ {1,2}but differ for q≥3. This example also shows that whether a graph is 2-connected cannot be determined by the 2-state Potts partition function. On the other hand, since F(G;2,1)=2|E|−|V|+k(G)and F(G;2,x)=2−|V|(x−1)|E|PG;2,x+1 x−1, we can decide whether Gis connected given P(G;2,y), and more generally find k(G). An example of a pair of graphs that are both simple and share the same 2-state Potts partition function is given in Fig. 2 (taken from Fig. 3 in [2]). The value of the chromatic polynomial P(G;q) for these two graphs differs by q(q−1)2(q−2). Hence the graphs in Fig. 2 have different q-state Potts model partition functions for q≥3. We have not yet found for any q≥3 an example of a pair of graphs with the same q-state Potts model partition function but different 2-state Potts model partition function. Lemma 14. Let G =(V,E)be a connected graph. The 2-state Potts partition function P(G;2,y) determines the following graph parameters: (i) |V|and |E|; (ii) for each 0≤k≤ |E|the number of Eulerian subgraphs of size k, in particular, the girth g(G)of G and the number of cycles of this size; whether G is simple and, if so, the number of triangles; (iii) for each 0≤k≤ |E|the number of cutsets of size k, in particular, the edge connectivity λ(G)of G and whether G is cosimple; (iv) whether G is bipartite and whether G is Eulerian. Proof. Part (i) follows since P(G;2,1)=2|V|and the degree of P(G;2,y)in yis |E|. For (ii) and (iii), we use Lemma 13. The coefficient of y|E|−kin 2−1P(G;2,y)is equal to the number of cutsets of size k. The polynomial F(G;2,x)can be recovered from P(G;2,y)by setting x=y+1 y−1, and the coefficient of x|E|−kin F(G;2,x)is equal to the number of Eulerian subgraphs of size k. Given that Gis simple (has no 1-edge or 2-edge cycles), a 3-edge Eulerian subgraph must be a triangle. An Eulerian subgraph of minimal size g(G)is a cycle so the coefficient of x|E|−g(G)is equal to the number of cycles of size g(G) in the graph of this girth. For part (iv), a graph Gis bipartite if and only if P(G;2,0)= 0, and Gis Eulerian if and only if F(G;2,0)=(−1)|E|2−|V|P(G;2,−1)= 0.  A list of parameters similar to Lemma 14 that are determined by chromatic polynomial has been instrumental in proving chromatic uniqueness results. Fig. 3. Graphs with different chromatic number and different clique number but the same 2-state Potts partition function. Lemma 15 ([24]).Let G =(V,E)be a connected simple graph. The chromatic polynomial P(G;q) determines the following graph parameters: (i) |V|and |E|; (ii) whether G is 2-connected; (iii) the number of triangles, and |{chordless 4-cycles}| − 2|{4-cliques}|; (iv) the girth g(G)and the number of cycles of this size; (v) the chromatic number χ(G). Duan et al. [13] provide an analogous list of flow polynomial invariants that suffices to prove their uniqueness results. Lemma 16 ([13, Theorem 3.1]).Let G =(V,E)be a connected cosimple graph. The flow polynomial F(G;q)determines the following graph parameters: (i) |V|and |E|; (ii) whether G is 2-connected; (iii) the edge connectivity λ(G)and the number of bonds of this size; (iv) the flow number φ(G). The corresponding list of parameters determined by the Tutte polynomial (see for example [30, Lemma 3.9]) that has been used to prove Tutte uniqueness results [29,11,18] starts with the union of the lists given in Lemmas 15 and 16. An important addition is that T(G;x,y)determines the number of cliques of any given size in G, in particular the clique number ω(G). Further, T(G;x,y)determines the number of 4-cycles and 5-cycles of G, and amongst the 4-cycles the number that have exactly one chord. The latter refines the knowledge obtained from the chromatic polynomial concerning 4-cycles, namely the quantity in Lemma 15(iii). Read and Whitehead [31] showed that the Tutte polynomial cannot only tell whether Gis simple or cosimple but for each 0 ≤k≤ |E|also gives the number of edges of multiplicity kand the number of ‘‘chains’’ (maximal class of edges in series) of length k. The pair of graphs in Fig. 1 show that the 2-state Potts model can do no better than detect whether a graph is simple. The chromatic number χ(G)is not determined by P(G;2,y)(except for deciding whether χ(G)= 2), and the flow number φ(G)is not determined by P(G;2,y)(except for deciding whether φ(G)=2). Also, the clique number ω(G)is not determined by P(G;2,y)(except for deciding whether ω(G)=2). The graphs in Fig. 3 (which are the same as those of Fig. 4 in [2]) have different chromatic numbers and different clique numbers but the same 2-state Potts partition function. 3.4. Examples of q-state Potts unique graphs The q-state Potts partition function for q≥3 contains a lot of the information that can be obtained from the 2-state Potts partition function (Lemma 14). Lemma 17. The q-state Potts partition function P(G;q,y)determines the following parameters of a graph G: (i) |V(G)|,|E(G)|,k(G); (ii) the girth g(G)and the number of cycles of this length; if g(G)≥3(i.e., G is simple) then whether G is bipartite; (iii) the edge connectivity λ(G)and the number of cutsets of this size; if λ(G)≥3(i.e., G is cosimple) then whether G is Eulerian; Table 1 Evaluations of graph polynomials from counting homomorphisms. Hhom(G,H) KqChromatic polynomial, P(G;q) Ky qq-state Potts partition function, P(G;q,y) Ky qqk(G)y|E| K1 1+Kq−1Independence polynomial, I(G;q−1) K1 q−1+K1(q−1)|V|I(G;(q−1)−1) K1 p+Kq−pBivariate independence polynomial, I(G;p,q−p) K1 p+Ky q−p[p=1,y=1 is the Widom–Rowlinson model] K1 p+Ky q−p K1 q−p+KpDohmen–Pönitz–Tittmann polynomial [12] at (p,q) K1 q−p+Ky pAverbouch–Godlin–Makowsky polynomial [3] at (q,y−1, (p−q)(y−1)) K1 q−p+Ky p The graph parameter hom(G,K1 q−p+Kp)when p=1 is equal to the independence polynomial of G. As remarked above, taking 1 ≤p≤qgives evaluations of the Dohmen–Pönitz–Tittmann polynomial. This in turn is the case y=0 of the graph parameter hom(G,K1 q−p+Ky p)=− U⊆V (q−p)|U|P(G−U;p,y), shown in Theorem 34 to be an evaluation of the Averbouch–Godlin–Makowsky polynomial. Recall that hom(G,K1 p+Kq−p)=I(G;q−p,p). Putting loops of weight yon each of the q−p vertices in the (q−p)-coclique gives K1 p+Ky q−p. For a graph G, hom(G,K1 p+Ky q−p)=∑ U⊆V(G) p|U|(q−p)k(G−U)y|E(G−U)| =∑ induced subgraphs Hof G p|V(G)|−|V(H)|(q−p)k(H)y|E(H)|. When p=1=y,hom(G,K1 1+K1 q−1)is the partition function of the Widom–Rowlinson model [37] (see also [15]). Table 1 summarizes the polynomial graph invariants obtained by counting homomorphisms to cliques or cocliques with loops of constant weight attached to their vertices, and the various joins of these graphs. For the blank entries in this table there is obviously a state sum formula for hom(G,H) similar to that given above for hom(G,K1 p+Ky q−p), but we could not find a well-known interpretation for it. 4.3. The Averbouch–Godlin–Makowsky polynomial Averbouch, Godlin and Makowsky [3] introduce their polynomial ξ(G;x,y,z)as a simultaneous trivariate generalization of the Tutte polynomial and matching polynomial. The polynomial ξ(G;x,y,z)includes the polynomial of Dohmen et al. [12] as the specialization ξ(G;q,−1,q−p). The q-state Potts partition function P(G;q,y)is the specialization ξ(G;q,y−1,0). For edge e=uv, GĎedenotes the induced graph G− {u, v}. The polynomial ξ(G)is defined by the following confluent recurrence relation [3]: ξ(P0;x,y,z)=1, ξ(P1;x,y,z)=x, ξ(G⊕H;x,y,z)=ξ(G;x,y,z)ξ(H;x,y,z), ξ(G;x,y,z)=ξ(G\e)+yξ(G/e;x,y,z)+zξ(GĎe;x,y,z). (10) (The boundary conditions are for the empty graph P0and a single isolated vertex P1.) Theorem 34. For all graphs G, hom(G,K1 q−p+Ky p)=ξ(G;q,y−1, (p−q)(y−1)). (11) Proof. We check that the recurrence (10) is satisfied by hom(G,K1 q−p+Ky p)with the appropriate values of the three arguments of ξ(G). Eq. (11) holds trivially for G=P0,P1. Also, both leftand right-hand sides of Eq. (11) are multiplicative over disjoint unions. It remains to prove that hom(G,K1 q−p+Ky p)satisfies the recurrence relation (10). Let Qbe a set of size qand P⊆Qsize p. Let G=(V,E)and e=uv∈E. Partition the range of summation in hom(G,K1 q−p+Ky p)=− φ:V→Q y|{ij∈E:φ(i)=φ(j)∈P}| (12) into three classes according as φ(u)= φ(v), φ(u)=φ(v) ∈ Por φ(u)=φ(v) ∈P. For short, let us write here h(G)for the function hom(G,K1 q−p+Ky p). Restricting the summation (12) to each of these classes separately, − φ:V→Q φ(u)=φ(v) y|{ij∈E:φ(i)=φ(j)∈P}| =h(G\e)−h(G/e), − φ:V→Q φ(u)=φ(v)∈P y|{ij∈E:φ(i)=φ(j)∈P}| =(q−p)h(GĎe), and − φ:V→Q φ(u)=φ(v)∈P y|{ij∈E:φ(i)=φ(j)∈P}| =yh(G/e)−y(q−p)h(GĎe). (If φ(u)=φ(v) ∈ Pthen all contributions to the weight of the vertex colouring φfrom edges incident with eare 1, so the weight of φis the same as the weight of φrestricted to V\ {u, v}. There are q−p choices for the colour φ(u)=φ(v) ∈ Pon the endpoints of e.) Hence h(G)=h(G\e)−h(G/e)+(q−p)h(GĎe)+yh(G/e)−y(q−p)h(GĎe) =h(G\e)+(y−1)h(G/e)+(p−q)(y−1)h(GĎe). Thus h(G)is the evaluation of ξ(G)at the point (q,y−1, (p−q)(y−1)). We now prepare to prove a converse to Theorem 34. As in [19], the key lemma is the following elementary result. Lemma 35. Let u1,...,urbe distinct non-zero complex numbers and ℓ∈Z>0. Suppose that, for ℓ≤k≤ ℓ+r−1, c1uk 1+c2uk 2+ · · · + cruk r=0. Then c1=c2= · · · = cr=0. Lemma 36. Let H be an edge-C-weighted graph on q vertices and x,y,z∈C. If hom(G,H)=ξ(G;x, y,z)for all G ∈ {Kk,0 1:k∈Z>0}then there is an integer p,0≤p≤q, such that (i) x=q and z =(p−q)y, (ii) the weights on p loops of H are equal to 1+y and the weights on the remaining q −p loops of H are equal to 1. Proof. The graph K0,0 1is an isolated single vertex. We have ξ(K0,0 1;x,y,z)=xand hom(K0,0 1,H)= |V(H)| = q. Let Hon vertex set [q]have adjacency matrix A=(au,v). Let ℓk=ξ(Kk,0 1;q,y,z). Using the recurrence relation (10) for ξ(G), for k≥1 we have ℓk=(1+y)ℓk−1+z. With boundary condition ℓ0=q, it follows that ℓk=ξ(Kk,0 1;q,y,z)=(q+zy−1)(1+y)k−zy−1when y= 0 and ξ(Kk,0 1;q,0,z)=q+kz when y=0. Assume first that y= 0. By hypothesis, hom(Kk,0 1,H)=− v∈[q] ak v,v =(q+zy−1)(1+y)k−zy−1. By Lemma 35, with u1,...,urtaking the distinct non-zero values amongst {av,v :v∈ [q]}∪{1+y,1}, it follows that zy−1∈Zand, setting p=q+zy−1, that |{v∈ [q] : av,v =1+y}| = pand |{v∈ [q] : av,v =1}| = q−p. The statement of the lemma results. When y=0, ℓk=q+kz, and since this is also equal to ∑ak v,v it follows that z=0 and av,v =1 for each v∈ [q]. So in this case the statement of the lemma holds with p=q(or p=0).  We reach our desired converse to Theorem 34. Theorem 37. Let H be an edge-C-weighted graph on q vertices and x,y,z∈C. If hom(G,H)= ξ(G;x,y,z)for all G ∈ {Kk,0 1,K0,k 2:k∈Z>0}then there is an integer p,0≤p≤q, such that (i) x=q∈Z>0,z=(p−q)y, (ii) H∼ =K1 q−p+K1+y p. Proof. By Lemma 36, we have x=q,z=(p−q)y, and ploops of Hwith weight 1 +yand q−ploops with weight 1. It remains to determine the weights on the non-loop edges of H. Let mk=ξ(K0,k 2;q,y, (p−q)y). Using the recurrence relation (10),mk=mk−1+yℓk−1+(p−q)y, with boundary value m0=q2. Since ℓk=(1+y)ℓk−1+(p−q)y, ℓ0=q, we have mk−mk−1= ℓk−ℓk−1, from which we obtain mk=ℓk+q2−q=p(1+y)k+q2−p. By hypothesis, we also have hom(K0,k 2,H)=− (u,v)∈[q]×[q] ak u,v =p(1+y)k+q2−p. Lemma 35 implies that |{(u, v) ∈ [q] × [q] : au,v =1+y}| = pand |{(u, v) ∈ [q] × [q] : au,v =1}| = q2−p. The result follows. (The case y=0 is trivial, corresponding to all edges, loops and non-loops, of weight 1.)  Remark 2. Averbouch et al. [3, Theorem 6] take a vertexand edge-weighted graph Hon vertex set [q]having pvertices of weight −1 with attached loops of weight 1, and the remaining vertices of weight 1 with loops of weight 1 +y. They show that hom(G,H)=ξ(G;q−2p,y,py); indeed, a simple adaptation of the proof of Theorem 34 can be used to demonstrate this result. (In the edge elimination reduction GĎe, if the endpoints of eare the same colour and not in Pthen each vertex has weight −1 and all incident edges weight 1, so there is no overall weight change upon extracting the edge e.) This raises the question as to what are possible choices for Hwhen it is allowed to have both vertex and edge weights, i.e., what is the analogue of Theorem 37 in this situation? 4.4. The Tittmann–Averbouch–Makowsky polynomial In order to study the polynomial Q(G;x,y)of Tittmann et al. [33], we will find it convenient to first define homomorphisms between coloured graphs. Ak-coloured graph (G, κ) is a (possibly weighted) graph Gtogether with a function κ:V(G)→ [k] assigning a colour κ(v) to each vertex v. (The colouring κis not necessarily proper.) A colour-preserving homomorphism from (G, κ) to (H, κ0)is a homomorphism f:V(G)→V(H)with the property that κ0(f(v)) =κ(v) for each v∈V(G). Given a multigraph G, edge-weighted graph Hwith edges ij of weight βij, and k-colourings κ: V(G)→ [k], κ0:V(H)→ [k], define hom c((G, κ), (H, κ0)) =− f:V(G)→V(H) κ0f=κ∏ uv∈E(G) βf(u)f(v), which for a multigraph H(βij ∈Z≥0) is equal to the number of colour-preserving homomorphisms (G, κ) →(H, κ0). Fig. 6. The graph Hk,x,y,z. This can be viewed as an ornamented star K1,y: the central vertex is replaced by ktwin vertices forming a clique with loops on each vertex, all edges having weight 1. The ypendant vertices are replaced by x-cliques, with loops of weight zattached to each vertex. The single lines joining cliques each stand for kx edges joining all pairs of vertices between K1 kand Kz x. All edges are of weight 1 unless otherwise indicated. The case z=1 is the graph of [33, Figure 6], for which hom(G,Hk,x,y,1)=k|V(G)|Q(G;x/k,y). The case y=1 gives – after renaming parameters – the graph in Fig. 7. Given a colour-preserving homomorphism f:G→Hand a fixed colouring κ0:V(H)→ [k], the condition f−1(κ−1 0(c)) =κ−1(c)for each c∈ [k]partitions the set of all homomorphisms f:G→H according to the colouring κ. Hence, for any fixed κ0:V(H)→ [k], − κ:V(G)→[k] hom c((G, κ), (H, κ0)) =hom(G,H). (13) (Cf. Eq. (2) in [28].) In [33], Tittmann et al. define the ‘induced subgraph polynomial’ of a graph G=(V,E)as follows: Q(G;x,y)=− U⊆V x|U|yc(G[U]), where G[U]is the induced subgraph on Uand c(G[U])the number of its connected components. They show that Q(G;x,y)for x∈Rand y∈Z≥0can be viewed as a partition function by counting graph homomorphisms to a vertexand edge-weighted graph, but leave it as an open problem whether there are other points (x,y)for which Q(G;x,y)is equal to a homomorphism number. Our main result towards which we work in this section is Theorem 47, which answers this question for homomorphisms to graphs with positive real vertex weights and complex edge weights. Let Hk,x,ybe the graph formed by taking K1 kas the centre of a star with yvertices of degree 1 each replaced by a copy of K1 x(the graph Staryof [33, Figure 6] with vertices of weight xreplaced by xtwin vertices forming K1 xand with the root replaced by ktwin vertices forming K1 k). This is the graph Hk,x,y,z illustrated in Fig. 6 above with z=1. By Theorem 10 in [33], hom(G,H1,x,y)is equal to the polynomial Q(G;x,y). It is not difficult to see that, more generally, hom(G,Hk,x,y)=k|V(G)|Q(G;x/k,y). Let κ0:V(Hk,x,y)→ [k] ∪ {0} → be a colouring which restricted to K1 kis an injection V(K1 k)→ [k] and which colours all the other xy vertices in the looped cliques K1 xwith the colour 0. Then, for any colouring κ:V(G)→ [k]∪{0}, hom c((G, κ), (Hk,x.y, κ0)) =hom(G[κ−1(0)],yK1 x) (where yK1 xdenotes ydisjoint copies of K1 x), since each colour in [k]occurs just once in (Hk,x,y, κ) and on the looped clique K1 k, so there is precisely one colour-preserving homomorphism from G−κ−1(0) to Hk,x,y, and this has weight 1. Setting U=κ−1(0), this gives hom c((G, κ), (Hk,x.y, κ0)) =yc(G[U])∏ 1≤i≤c(G[U]) hom(Gi,K1 x) =yc(G[U])x|U|, where G1,...,Gc(G[U])are the connected components of G[U], containing altogether |U|vertices. By Eq. (13), hom(G,Hk,x,y)=− κ:V(G)→[k]∪{0} x|κ−1(0)|yc(G[κ−1(0)]) =− U⊆V(G) x|U|yc(G[U])k|V(G)|−|U| =k|V(G)|Q(G;x/k,y). By the same argument, if we take Hk,x,y,zto be the graph in Fig. 6 with loop weights zinstead of 1 on each of the cliques Kx, then hom(G,Hk,x,y,z)=− U⊆V(G) yc(G[U])k|V(G)|−|U|∏ 1≤i≤c(G[U]) hom(Gi,Kz x) =− U⊆V(G) k|V(G)|−|U|yc(G[U])∏ i P(Gi;x,z) =− U⊆V(G) k|V(G)|−|U|yc(G[U])(z−1)r(G[U])xc(G[U])∏ i TGi;z−1+x z−1,z =k|V(G)|− U⊆V(G)x k|U|xy z−1c(G[U]) ∏ 1≤i≤c(G[U]) TGi;z−1+x z−1,z. This polynomial in k,x,y,zincludes the Averbouch–Godlin–Makowsky polynomial ξ(G;x,y,z) and the Tittmann–Averbouch–Makowsky polynomial Q(G;x,y)as specializations. (See Figs. 6 and 7.) We now return to the latter and settle the question of when an evaluation of Q(G;x,y)is equal to a homomorphism number hom(G,H). We do this first for Hwith positive integer vertex weights and complex edge weights, and then deduce the result for Hwith positive real vertex weights and complex edge weights. We require a number of lemmas to obtain our first result in Theorem 44. Note that Q(G;x,y)does not distinguish parallel edges, nor do loops contribute anything, so that Q(G;x,y)=Q(G′;x,y), where G′is the simple graph obtained from Gby removing all but one edge in each parallel class and removing any loops. Recall that Kk,0 1denotes the graph consisting of kloops on a single vertex and K0,k 2two vertices joined by kparallel edges. Lemma 38. For k ∈Z>0,Q(Kk,0 1;x,y)=xy +1and Q (K0,k 2;x,y)=x2y+2xy +1. Proof. By direct calculation, Q(Kk,0 1;x,y)=Q(K1;x,y)=xy +1 and Q(K0,k 2;x,y)=Q(K2;x,y)= x2y+xy +1.  Lemma 39. For k ∈Z>0, Q(K1,k;x,y)=(xy +1)k+xy(x+1)k, Q(Pk;x,y)=1−x+a 2ax+1+a 2k+1 −1−x−a 2ax+1−a 2k+1 , where a =(x−1)2+4xy. Proof. The first identity is given in [33, Corollary 19]. The second identity is the one given after Proposition 16 in [33], just written differently.  Fig. 7. The graph K1 q−p+Ky p. The line between the cliques stands for the (q−p)pedges joining them. This graph is a special case of the ornamented star of Fig. 6. An evaluation of the Averbouch–Godlin–Makowsky polynomial is given by hom(G,Kq−p+Ky p)=ξ(G;q,y−1, (p−q)(y−1)). Lemma 40 (See e.g. [20, Ch. 8, Ex. 20]).If A=ab⊤ bB then det(tI −A) det(tI −B)=t−a−b⊤(tI −B)−1b =t−a−− θ∈ev(B) b⊤Eθb t−θ, where ev(B)denotes the set of distinct eigenvalues of B and Eθis the orthogonal projection onto the eigenspace of vectors with eigenvalue θ. We write φA(t)=det(tI −A)for the characteristic polynomial of A(of the graph whose adjacency matrix is A). Corollary 41. Let B =Iy⊗Jxand A=11⊤ 1B. Then φA(t) φB(t)=t2−(x+1)t−x(y−1) t−x, so that, writing a =(x−1)2+4xy, the eigenvalues of A are 1 2(x+1+a)(with multiplicity 1), 1 2(x+1−a)(multiplicity 1), x (multiplicity y −1) and 0(multiplicity xy −y). Proof. By Lemma 40, φA(t) φB(t)=t−1−1⊤Ex1 t−x−1⊤E01 t, where Ex=(xy)−1Jxy,E0=Ixy −Ex, and 1⊤Ex1=xy,1⊤E01=0. This gives φA(t)=t−1−xy t−xφB(t) = [t2−(x+1)t−x(y−1)](t−x)y−1txy−y, with the matrix B=Iy⊗Jxhaving characteristic polynomial φB(t)=(t−x)ytxy−y. Lemma 42. Suppose that H is a graph such that 1. there is an apex vertex v0attached to all the other vertices, 2. there are a ≥0loops on v0, and 3. H−v0is a spectrally unique x-regular graph with adjacency matrix B. Then H is determined up to isomorphism to be the graph with adjacency matrix A=a1⊤ 1B. Proof. Since H−v0is x-regular, Bhas eigenvector 1with eigenvalue x, and any other eigenvector of Bwith eigenvalue θdifferent to xis orthogonal to 1. If Eθis the projection onto the θ-eigenspace of B then 1⊤Eθ1=xθ=x, 0θ= x. By Lemma 40, φA(t)=φB(t)[t−a−xt t−x]. Hence if H−v0is uniquely determined by its characteristic polynomial φB(t)then His also determined by its characteristic polynomial φA(t). Lemma 43. For k ∈Z>0, Q(Ck;x,y)=x+1+a 2k +x+1−a 2k +(y−1)xk, where a2=(x−1)2+4xy. Proof. By [33, Theorem 10] and Lemma 26,Q(Ck;x,y)=hom(Ck,H1,x,y)=tr(Ak), where Ais the adjacency matrix of H1,x,y. The eigenvalues of the matrix Aare calculated in Corollary 41. We are now ready to prove our first main result about for which points (x,y)the evaluation Q(G;x,y)is equal to a homomorphism number hom(G,H), and which graphs Hyield these evaluations. Theorem 44. Let (H, α, β) be a weighted graph, where α:V(H)→Z>0and β:E(H)→C. Then hom(G,H)=Q(G;x,y)for some point (x,y)if and only if x,y∈Z≥0and H ∼ =H1,x,yup to twin vertices. Proof. Note that H1,x,0is the empty graph (equivalently, all its vertices have weight 0) and H1,0,y= K1 1; we have Q(G;0,y)=1=hom(G,K1 1)and Q(G;x,0)=0. Henceforth, we assume that xand y are non-zero. The condition ‘‘up to twin vertices’’ is needed because a vertex of Hwith weight acan be split into twin vertices whose vertex weights sum to awithout affecting hom(G,H). Upon splitting vertices with positive integer weight ainto aunweighted twin vertices (i.e., weight 1), we just need to prove the statement for an edge-weighted graph (H, β). Suppose that hom(G,H)=Q(G;x,y)for some non-zero x,y∈C. Since Q(P1;x,y)=xy +1, we have |V(H)| = xy +1. Since hom(Kk,0 1,H)=∑v∈V(H)βk v,v =xy +1, it follows that βv,v =1 for each v. For each k∈Z>0, hom(K0,k 2,H)=− (u,v)∈V(H)×V(H) βk u,v =x2y+2xy +1.(14) This forces βu,v ∈ {0,1}for each (u, v) ∈V(H)×V(H). There are (xy+1)2pairs (u, v) ∈V(H)×V(H) and x2y+2xy +1=(xy +1)2−x2y(y−1). We have seen that the xy +1 loops each have weight 1. There are thus x2y 2non-edges uv(weight βu,v =0), and the remaining x+1 2ynon-loop edges uv also have weight βu,v =1. By Lemma 39, hom(K1,k,H)=− v∈V(H)− u∈V(H) βu,vk =1·(xy +1)k+xy(x+1)k, which implies that there is a single apex vertex v0for which ∑u∈V(H)βu,v0=xy +1, and ∑u∈V(H)βu,vi=x+1 for the remaining xy vertices v1, v2, . . . , vxy. By Lemma 43, hom(Ck,H)=− θ∈ev(A) θk=x+1+a 2k +x+1−a 2k +(y−1)xk, where the sum ranges over eigenvalues θof the adjacency matrix A=(βu,v)of H, taken with multiplicity. Hence the eigenvalues of Aare 0 (multiplicity xy −y), x(multiplicity y−1), and one eigenvalue is equal to 1 2(x+1+a), and one equal to 1 2(x+1−a). We have thus seen that, by taking Gin the family {Kk,0 1,K0,k 2,K1,k,Ck:k∈Z>0}, the homomorphism numbers hom(G,H)determine that the adjacency matrix of Ais a (0,1)-matrix (so His an unweighted graph) of size xy +1 and rank y+1, each entry in the diagonal equal to 1, one vertex v0 indexing a row and column all of whose entries are equal to 1, and each of the other rows and columns containing x+1 non-zero entries. Finally, the spectrum of Hcoincides with that of H1,x,y. The complete graph K1 xwith a loop on each of its vertices is uniquely determined by its characteristic polynomial tx−1(t−x)amongst unweighted graphs. The disjoint union of ycopies of this graph, which has adjacency matrix Iy⊗Jx, is then also uniquely determined by its characteristic polynomial txy−y(t−x)yamongst unweighted graphs (see for example [35, Proposition 5]). Since Hhas an apex vertex of degree xy +1 whose deletion leaves an x-regular graph, and since its spectrum determines that its adjacency matrix Asatisfies φA(t)=φIy⊗Jx(t)t−1−xt t−x,Lemma 42 implies that Hmust be isomorphic to H1,x,y. Theorem 44 can be extended from α:V(H)→Z>0to α:V(H)→R>0as follows. Lemma 45. If (H, α, β) is a weighted graph with α:V(H)→Z>0and β:E(H)→Csuch that hom(G,H)=k|V(G)|Q(G;x/k,y)then H ∼ =Hk,x,yup to twin vertices. Proof. The proof is by simple adaptation of proof of Theorem 44. Corollary 46. If (H, α, β) is a weighted graph with α:V(H)→Q>0and β:E(H)→Cthen hom(G,H)=Q(G;x,y)for some point (x,y)if and only if H ∼ =H1,x,yup to twin vertices. Proof. Suppose that the least common multiple of the denominators of the vertex weights is equal to k. Multiply through the vertex weights of Hby kto obtain a vertex-Z>0-weighted graph H′. Then hom(G,H)=Q(G;x,y)if and only if hom(G,H′)=k|V(G)|Q(G;x,y), and by Lemma 45 the latter holds if and only if H′∼ =Hk,kx,yup to twin vertices. Then H∼ =H1,x,yup to twin vertices.  Theorem 47. If (H, α, β) is a weighted graph with α:V(H)→R>0and β:E(H)→Cthen hom(G,H)=Q(G;x,y)for some point (x,y)if and only if H ∼ =H1,x,yup to twin vertices. Proof. Let ((Hn, αn, β) :n=1,2, . . .) be a sequence of vertexand edge-weighted graphs where the functions αn:V(Hn)→Q>0 have the property that αn(v) →α(v) for each v∈V(H)=V(Hn), i.e., (αn)converges pointwise to α. By continuity of Q(G;x,y)in xand hom(G,Hn)→hom(G,H)= Q(G;x,y), there must be a sequence of reals (xn)convergent to xsuch that hom(G,Hn)=Q(G;xn,y). By Corollary 46,Hn∼ =H1,xn,yup to twin vertices, and taking the limit as n→ ∞ we get H∼ =H1,x,yup to twin vertices.  Now, let H=(H, α, β) be a vertexand edge weighted graph, with α:V(H)→C(and as usual β:V(H)→C). We do not have any examples of (H, α, β) where αtakes negative values and for which hom(G,H)=Q(G;x,y). On the other hand, as noted in Remark 2 above, Averbouch et al. do obtain such an example for their ‘‘edge elimination polynomial’’ ξ(G;x,y,z). Tittmann et al. [33] pose a slightly weaker problem than determining whether there is a vertexand edge-weighted graph Hnot isomorphic up to twins with H1,x,ysuch that hom(G,H)=Q(G;x,y): what they ask is whether there is a point (x,y)with y∈ Z≥0for which hom(G,H)=Q(G;x,y)for some H. To this question we do have an answer. Lemma 48. If hom(Ck,H)=Q(Ck;x,y)for k ∈Z>0then the eigenvalues of the matrix C=((αuαv)1 2βu,v)u,v∈V(H)are x (y−1times), (x+1+a)/2(once) (x+1−a)/2(once) and 0(|V(H)|−y−1 times), where a2=(x−1)2+4xy. Proof. We have hom(Ck,H)=− v0,v1,...,vk−1,vk=v0 αv0αv1· · · αvk−1βv0,v1βv1,v2· · · βvk−1,v0 =− v0,v1,...,vk−1,vk=v0∏ 0≤i≤k−1 (αviαvi+1)1 2βvi,vi+1 =tr(Ck) =− θ∈ev(C) θk=x+1+a 2k +x+1−a 2k +(y−1)xk, where ev(C)denotes the multiset of eigenvalues of C. Corollary 49. If Q (G;x,y)=hom(G,H)for some vertexand edge-weighted graph H then y ∈Z>0or y=0and H has vertices all of weight 0. 4.5. ‘Local Tutte–Grothendieck invariants’ A ‘G-local Tutte–Grothendieck invariant’ is just required to satisfy the generalized Tutte–Grothendieck recurrence relations for a minor-closed class of graphs G, not necessarily all graphs. This includes the case of parameters of the form h(G)T(G;x,y)for a G-local function h, since these satisfy a generalized Tutte–Grothendieck recurrence relation for G∈G. Our main result in this section is Theorem 53, which proves that if a homomorphism number is a generalized Tutte–Grothendieck invariant locally on cycles, paths, multiple edges and multiple loops then it is in fact a Tutte–Grothendieck invariant on all multigraphs, and hence is of the form hom(G,Ka,b q), where Ka,b qis a Potts model graph. Tutte–Grothendieck invariants have recurrence relations that vary depending on whether an edge is a bridge, loop or ordinary. However, it turns out that if a generalized Tutte–Grothendieck invariant is also equal to hom(G,H)for a connected edge-weighted graph Hthen in fact there is no dependence on edge type.2A familiar example is the evaluation of the chromatic polynomial hom(G,Kq). Note however that, by multiplying by a suitable local function, any generalized Tutte–Grothendieck invariant can be made to satisfy a contraction–deletion recurrence that is independent of edge type. For example, the flow polynomial F(G;q)satisfies F(G)=     F(G/e)−F(G\e)eordinary, 0ea bridge, (q−1)F(G\e)ea loop, 1E= ∅. Here, h(G)=q|V|F(G;q)satisfies h(G)=qh(G/e)−h(G\e)for all edges eof G. Lemma 50. Let H be an edge-C-weighted graph on q vertices and α, β, x,y∈C. Suppose that for G∈ {Kk,0 1,K0,k 2:k∈Z>0}the function hom(G,H)=h(G)satisfies the equations for a generalized 2Averbouch et al. [3, p.4, n.2] remark that the recurrence relation for the polynomial ξ(G)does not depend on the type of edge being contracted/deleted/eliminated, and that it may be interesting to explore the possibility of dependence on edge type. Theorem 37 would in fact incorporate this more general situation, due to the fact that for connected Hhomomorphism functions hom(G,H)do not satisfy recurrences dependent on edge type. Tutte–Grothendieck invariant, i.e., h(G)=         αh(G/e)+βh(G\e)e ordinary, xh(G/e)e a bridge, yh(G\e)e a loop, q G =K0,0 1, q2G=K0,0 2. Then when y = βthe graph H has q loops on each of its vertices, each loop of weight y,q(α+β−y) y−βordinary edges of weight y,q(α+qβ−x) βordinary edges of weight 0 (zero) and the remaining ordinary edges of weight β. If y =βthen α=0,x=y,H=Ky qand hom(G,H)=qk(G)y|E|. Proof. Let Hhave adjacency matrix A=(au,v)u,v∈[q]. Then, for each k∈Z>0, h(Kk,0 1)=hom(Kk,0 1,H)=− v∈[q] ak v,v, and also h(Kk,0 1)=qyk. By Lemma 35, this implies that av,v =yfor each v∈ [q]. For each k∈Z>0, we also have h(K0,k 2)=hom(K0,k 2,H)=− (u,v)∈[q]×[q] ak u,v, and, by the recurrence relations, for k≥2, h(K0,k 2)=αh(Kk−1,0 1)+βh(K0,k−1 2), with boundary condition h(K0,1 2)=qx. Writing mk=h(K0,k 2), for k≥2, mk=βmk−1+αqyk−1,m1=qx. Set M(t)=∑k≥1mktk−1. Then M(t)−qx =βtM(t)+αqy 1−yt , whence, for y= β, M(t)=qx 1−βt+αqy (1−βt)(1−yt), =qx 1−βt−αβqy (y−β)(1−βt)+αqy2 (y−β)(1−yt). This gives, for k≥1, mk=qx −αqy y−ββk−1+αq y−βyk.(15) For y=β, we obtain mk=qxyk−1+αq(k−1)yk−1. This implies that α=0 and also implies the situation described in the last statement of the lemma. We return to the case y= β. Write N(y)= |{(u, v) ∈ [q] × [q] : au,v =y}| and N(β) = |{(u, v) ∈ [q] × [q] : au,v =β}|. By Lemma 35, Eq. (15) implies that N(y)=αq y−β