We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call
Holant polynomials
. We transform these problems into partition ...functions of abstract combinatorial structures known as
polymers
in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the
cluster expansion
to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
Harmonious colourings of graphs Drgas-Burchardt, Ewa; Gibek, Katarzyna
Discrete Applied Mathematics,
01/2017, Letnik:
217
Journal Article
Recenzirano
Odprti dostop
A λ-harmonious colouring of a graph G is a mapping from V(G) into {1,…,λ} that assigns colours to the vertices of G such that each vertex has exactly one colour, adjacent vertices have different ...colours, and any two edges have different colour pairs. The harmonious chromatic numberh(G) of a graph G is the least positive integer λ, such that there exists a λ-harmonious colouring of G.
Let h(G,λ) denote the number of all λ-harmonious colourings of G. In this paper we analyse the expression h(G,λ) as a function of a variable λ. We observe that this is a polynomial in λ of degree ∣V(G)∣, with a zero constant term. Moreover, we present a reduction formula for calculating h(G,λ). Using reducing steps we show the meaning of some coefficients of h(G,λ) and prove the Nordhaus–Gaddum type theorem, which states that for a graph G with diameter greater than two h(G)+12χ(G2¯)≤∣V(G)∣, whereχ(G2¯) is the chromatic number of the complement of the square of a graph G. Also the notion of harmonious uniqueness is discussed.
A vertex subset W⊆V of the graph G=(V,E) is a total dominating set if every vertex of the graph is adjacent to at least one vertex in W. The total domination polynomial is the ordinary generating ...function for the number of total dominating sets in the graph. We investigated some graph products for a generalization of the total domination polynomial, called the trivariate total domination polynomial. We also show that the chromatic polynomial is encoded in the independent domination polynomial of some graph products. These results have a wide applicability to other domination related graph polynomials, e.g. the domination polynomial, the independent domination polynomial or the independence polynomial.
On Weakly Distinguishing Graph Polynomials Makowsky, Johann A; Rakita, Vsevolod
Discrete Mathematics and Theoretical Computer Science,
01/2019, Letnik:
21, Številka:
1
Journal Article
Recenzirano
Odprti dostop
A univariate graph polynomial P(G; X) is weakly distinguishing if for almost all finite graphs G there is a finite graph H with P(G; X) = P(H; X). We show that the clique polynomial and the ...independence polynomial are weakly distinguishing. Furthermore, we show that generating functions of induced subgraphs with property C are weakly distinguishing provided that C is of bounded degeneracy or treewidth. The same holds for the harmonious chromatic polynomial. Keywords: Graph Theory, Graph Polynomials
The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this ...computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and definability theory.
Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic
MSOL.
We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in
MSOL. Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically.
Finally, we discuss extensions of
MSOL for which the Feferman–Vaught Theorem holds as well.
In this paper we are interested in vertex partitioned ribbon graphs, which are a generalization of ribbon graphs that are studied in some theoretical physics models. We define a Hopf algebra of ...vertex partitioned ribbon graphs, then go on to describe how a natural generalization of the Bollobás-Riordan polynomial arises from this Hopf algebra. Using some appropriate Hopf algebraic characters we also prove the universality of our polynomial
Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and ...matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank ($R_2$-)polynomial and interlace polynomial. In particular Glauber dynamics for the $R_2$-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.
Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem ...there
Many graph polynomials, such as the Tutte polynomial, the interlace polynomial and the matching polynomial, have both a recursive definition and a defining subset expansion formula. In this article, ...we present a general, logic-based framework which gives a precise meaning to recursive definitions of graph polynomials. We then prove in this framework that every recursive definition of a graph polynomial can be converted into a subset expansion formula.
The dichromatic polynomial Z(G;q,v) can be characterized as the most general C-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion and edge contraction. ...Similarly, the universal edge elimination polynomial ξ(G;x,y,z) introduced in Ilya Averbouch, Benny Godlin, and Johann A. Makowsky. An extension of the bivariate chromatic polynomial. Eur. J. Comb, 31(1):1–17, 2010 can be characterized as the most general EE-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion, edge contraction and edge extraction. In this paper we examine substitution instances of ξ(G;x,y,z) and show that among these the dichromatic polynomial Z(G;q,v) plays a distinctive rôle.
PDF
