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 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.     

Generalized characteristic polynomials of graph bundles

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.     

A note on the matching numbers of triangle-free graphs

For the sake of brevity the absolute values of the coefficients of the matching polynomial of a graph are called matching numbers in this note. It is shown that for a triangle-free graph these numbers coincide with the coefficients of the chromatic polynomial of its complement when this polynomial is written in factorial form. As an application it is mentioned that the coefficients of every rook polynomial are at the same time coefficients of some chromatic polynomial.     

Partial duality and Bollobás and Riordan’s ribbon graph polynomial

Recently S. Chmutov introduced a generalization of the dual of a ribbon graph (or equivalently an embedded graph) and proved a relation between Bollobás and Riordan’s ribbon graph polynomial of a ribbon graph and of its generalized duals. Here I show that the duality relation satisfied by the ribbon graph polynomial can be understood in terms of knot theory and I give a simple proof of the relation which used the homfly polynomial of a knot.     

On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs

A main result in combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981). The circular-clique and circular-chromatic number are well-studied refinements of these graph parameters, and circular-perfect graphs form the corresponding superclass of perfect graphs. So far, it is unknown whether the (weighted) circular-clique and circular-chromatic number of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these two graph parameters for some super-classes of perfect graphs with the help of polyhedral arguments.     

Tutte uniqueness of line graphs

We prove that if a graph H has the same Tutte polynomial as the line graph of a d-regular, d-edge-connected graph, then H is the line graph of a d-regular graph. Using this result, we prove that the line graph of a regular complete t-partite graph is uniquely determined by its Tutte polynomial. We prove the same result for the line graph of any complete bipartite graph.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

On the Location of Roots of Graph Polynomials

Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the location of these roots reflects the graph theoretic properties of the underlying graph.     

矩阵特征多项式的图论计算公式

给出了赋权有向图邻接矩阵特征多项式的图论计算公式,从而得到了一般矩阵特征多项式的图论计算方法,并且研究了赋权有向图邻接矩阵特征多项式和谱半径的一些性质．     

The group and the minimal polynomial of a graph

This paper presents some results linking the minimal polynomial of the adjacency matrix of a graph with its group structure. An upper bound on the order of the group is derived for graphs whose minimal and characteristic polynomials are identical. It is also shown that for a graph with transitive group, the degree of the minimal polynomial is bounded above by the number of orbits of the stabilizer of any given element. Finally, the order of the group of a point-symmetric graph with a prime number of points is shown to depend on the degree of the minimal polynomial, and an algorithm for constructing such a group is given.     

A Penrose polynomial for embedded graphs

We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which cannot be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion–contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable chequerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G$G$ can be expressed as a sum of chromatic polynomials of twisted duals of G$G$. This allows us to obtain a new reformulation of the Four Colour Theorem.     

图和色多项式根2的阶

本文证明了3-连通非偶图的色多项式根2的阶为1;满足一定条件的非3-连通非偶图的色多项式根2的阶是图的非偶块和非偶可分块数.从而,把色多项式P(G)中1的阶是图G的非平凡块数这一结果进一步加以推广.     

The Growth of Limits of Vertex Replacement Rules

In this article, we give conditions to distinguish whether a vertex replacement rule given by a single graph H yields a limit graph having polynomial or exponential growth. In the case of polynomial growth, we compute the growth degree of the limit graph.     

图T1,1,m与Q(3,n)中有路因子的充分必要条件及T1,1,m的匹配等价类

如果一个图的匹配多项式可以被一个路的匹配多项式整除,我们就称此路是该图的一个路因子,路因子在刻画图的匹配等价类,研究匹配唯一性方面有很重要的作用.本文得到了图T1,1.m与图Q(3,n)中有路因子的充分必要条件.     

Some relations on Miyazawa's virtual knot invariant

Y. Miyazawa defined a polynomial invariant for a virtual link by using magnetic graph diagrams, which is related with the Jones-Kauffman polynomial. In this paper we show some relations of this polynomial for a virtual skein triple.     

A generalization of chromatic polynomial of a graph subdivision

Considering the partitions of a set into nonempty subsets, we obtain an expression for the number of all partitions of a given type. The chromatic polynomial of a graph subdivision is generalized, considering two sets of colors, and a general explicit expression is obtained for this generalization. Using these results, we determine the generalized chromatic polynomial for the particular case of complete graph subdivision.     

On chromatic coefficients

Explicit expressions in terms of subgraphs of the graph are given for the first five coefficients of the chromatic polynomial of a graph.     

On the location of zeros of the Laplacian matching polynomials of graphs

Journal of Algebraic Combinatorics - The Laplacian matching polynomial of a graph G, denoted by $$\mathscr {LM}(G,x)$$ , is a new graph polynomial whose all zeros are nonnegative real numbers. In...     

The bivariate Ising polynomial of a graph

In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.