On Graphs Determined by Their Tutte Polynomials

We say that a graph G is T-unique if any other graph having the same Tutte polynomial as G is necessarily isomorphic to G. In this paper we show that several well-known families of graphs are T-unique: wheels, squares of cycles, complete multipartite graphs, ladders, Möbius ladders, and hypercubes. In order to prove these results, we show that several parameters of a graph, like the number of cycles of length 3, 4 and 5, and the edge-connectivity are determined by its Tutte polynomial.Research partially supported by projects BFM2001-2340 and by CUR Gen. Cat. 1999SGR00356Final version received: January 10, 2003     

A Polynomial Invariant of Graphs On Orientable Surfaces

We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10.     

On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.     

On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique.     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

Topological Graph Polynomials in Colored Group Field Theory

In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph ${\mathcal{G}_{\partial}}In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph G_?{\mathcal{G}_{\partial}} of an open graph G{\mathcal{G}} and prove it is a cellular complex. Using this structure we generalize the topological (Bollobás–Riordan) Tutte polynomials associated to (ribbon) graphs to topological polynomials adapted to Colored Group Field Theory graphs in arbitrary dimension.     

Expansions for the Bollob��s-Riordan Polynomial of Separable Ribbon Graphs

We define 2-decompositions of ribbon graphs, which generalize 2-sums and tensor products of graphs. We give formulae for the Bollobás-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.     

A Characterization of the Tutte Polynomial via Combinatorial Embeddings

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte’s notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding. Received March 15, 2006     

Homomorphisms and Polynomial Invariants of Graphs

This paper initiates a study of the connection between graph homomorphisms and the Tutte polynomial. This connection enables us to extend the study to other important polynomial invariants associated with graphs, and closely related to the Tutte polynomial. We then obtain applications of these relationships in several areas, including Abelian Groups and Statistical Physics. A new type of uniqueness of graphs, strongly related to chromatically-unique graphs and Tutte-unique graphs, is introduced in order to provide a new point of view of the conjectures about uniqueness of graphs stated by Bollobas, Peabody and Riordan.     

Homomorphisms and polynomial invariants of graphs

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan.     

Invariants of Composite Networks Arising as a Tensor Product

We generalize Brylawski’s formula of the Tutte polynomial of a tensor product of matroids to colored connected graphs, matroids, and disconnected graphs. Unlike the non-colored tensor product where all edges have to be replaced by the same graph, our colored generalization of the tensor product operation allows individual edge replacement. The colored Tutte polynomials we compute exists by the results of Bollobás and Riordan. The proof depends on finding the correct generalization of the two components of the pointed Tutte polynomial, first studied by Brylawski and Oxley, and on careful enumeration of the connected components in a tensor product. Our results make the calculation of certain invariants of many composite networks easier, provided that the invariants are obtained from the colored Tutte polynomials via substitution and the composite networks are represented as tensor products of colored graphs. In particular, our method can be used to calculate (with relative ease) the expected number of connected components after an accident hits a composite network in which some major links are identical subnetworks in themselves.      

On the reconstruction of graph invariants

The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U-polynomial, the universal edge elimination polynomial ξ and the colored versions of the latter two are reconstructible.We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic.     

Orientations, Lattice Polytopes, and Group Arrangements I: Chromatic and Tension Polynomials of Graphs

This is the first one of a series of papers on association of orientations, lattice polytopes, and group arrangements to graphs. The purpose is to interpret the integral and modular tension polynomials of graphs at zero and negative integers. The whole exposition is put under the framework of subgroup arrangements and the application of Ehrhart polynomials. Such a viewpoint leads to the following main results of the paper: (i) the reciprocity law for integral tension polynomials; (ii) the reciprocity law for modular tension polynomials; and (iii) a new interpretation for the value of the Tutte polynomial T(G; x, y) of a graph G at (1, 0) as the number of cut-equivalence classes of acyclic orientations on G.     

The chromatic polynomial of fatgraphs and its categorification

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph. We extend our construction and categorify the Bollobás-Riordan polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.     

图的极大Tutte集的几个有效算法

图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.     

The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

On Tutte polynomial uniqueness of twisted wheels

A graph G is called T-unique if any other graph having the same Tutte polynomial as G is isomorphic to G. Recently, there has been much interest in determining T-unique graphs and matroids. For example, de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105-119; A. de Mier, M. Noy, Tutte uniqueness of line graphs, Discrete Math. 301 (2005) 57-65] showed that wheels, ladders, Möbius ladders, square of cycles, hypercubes, and certain class of line graphs are all T-unique. In this paper, we prove that the twisted wheels are also T-unique.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Counterexamples to a conjecture by Gross,Mansour and Tucker on partial-dual genus polynomials of ribbon graphs

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They computed these two partial-dual genus polynomials of four families of ribbon graphs, posed some research problems and made some conjectures. In this paper, we introduce the notion of signed interlace sequences of bouquets and obtain the partial-dual Euler genus polynomials for all ribbon graphs with the number of edges less than 4 and the partial-dual orientable genus polynomials for all orientable ribbon graphs with the number of edges less than 5 in terms of signed interlace sequences. We check all the conjectures and find a counterexample to the Conjecture 3.1 in their paper: There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient. Motivated by this counterexample, we further find an infinite family of counterexamples to the conjecture.