A logician's view of graph polynomials Makowsky, J.A.; Ravve, E.V.; Kotek, T.
Annals of pure and applied logic,
September 2019, 2019-09-00, Letnik:
170, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model ...theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.
Polynomial invariants for cactuses van Iersel, Leo; Moulton, Vincent; Murakami, Yukihiro
Information processing letters,
August 2023, 2023-08-00, Letnik:
182
Journal Article
Recenzirano
Odprti dostop
Graph invariants are a useful tool in graph theory. Not only do they encode useful information about the graphs to which they are associated, but complete invariants can be used to distinguish ...between non-isomorphic graphs. Polynomial invariants for graphs such as the well-known Tutte polynomial have been studied for several years, and recently there has been interest to also define such invariants for phylogenetic networks, a special type of graph that arises in the area of evolutionary biology. Recently Liu gave a complete invariant for (phylogenetic) trees. However, the polynomial invariants defined thus far for phylogenetic networks that are not trees require vertex labels and either contain a large number of variables, or they have exponentially many terms in the number of reticulations. This can make it difficult to compute these polynomials and to use them to analyse unlabelled networks. In this paper, we shall show how to circumvent some of these difficulties for rooted cactuses and cactuses. As well as being important in other areas such as operations research, rooted cactuses contain some common classes of phylogenetic networks such phylogenetic trees and level-1 networks. More specifically, we define a polynomial F that is a complete invariant for the class of rooted cactuses without vertices of indegree 1 and outdegree 1 that has 5 variables, and a polynomial Q that is a complete invariant for the class of rooted cactuses that has 6 variables whose degree can be bounded linearly in terms of the size of the rooted cactus. We also explain how to extend the Q polynomial to define a complete invariant for leaf-labelled rooted cactuses as well as (unrooted) cactuses.
•We introduce a complete polynomial invariant for rooted cactuses.•This invariant can be used to encode rooted cactuses, which can be used in the comparison of phylogenetic networks.•We extend the invariant to give a complete polynomial invariant for undirected cactuses and to leaf-labelled rooted cactuses.
In this article, we construct explicit examples of pairs of non-isomorphic trees with the same restricted U-polynomial for every k; by this we mean that the polynomials agree on terms with degree at ...most k+1. The main tool for this construction is a generalization of the U-polynomial to rooted graphs, which we introduce and study in this article. Most notably we show that rooted trees can be reconstructed from its rooted U-polynomial.
As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, ...this classical theorem exists some obvious shortcomings, for example, it requests all the roots of the corresponding generating function, which is impossible in general.
Aiming to overcome this shortcoming in some extent, in this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail. Some relevant conjectures, proposed by Godsil (Combinatorica, 1981) and Wang et al. (J. Math. Anal. Appl., 2017), are generalized and verified as corollaries.
Given a graph G in which each edge fails independently with probability q∈0,1, the all-terminal reliability of G is the probability that all vertices of G can communicate with one another, that is, ...the probability that the operational edges span the graph. The all-terminal reliability is a polynomial in q whose roots (all-terminal reliability roots) were conjectured to have modulus at most 1 by Brown and Colbourn. Royle and Sokal proved the conjecture false, finding roots of modulus larger than 1 by a slim margin. Here, we present the first nontrivial upper bound on the modulus of any all-terminal reliability root, in terms of the number of vertices of the graph. We also find all-terminal reliability roots of larger modulus than any previously known. Finally, we consider the all-terminal reliability roots of simple graphs; we present the smallest known simple graph with all-terminal reliability roots of modulus greater than 1, and we find simple graphs with all-terminal reliability roots of modulus greater than 1 that have higher edge connectivity than any previously known examples.
For a tree T, consider its smallest subtree T∘ containing all vertices of degree at least 3. Then the remaining edges of T lie on edge-disjoint paths each with one endpoint on T∘. We show that the ...chromatic symmetric function of T determines the size of T∘, and the multiset of the lengths of these incident paths. In particular, this generalizes a proof of Martin, Morin, and Wagner that the chromatic symmetric function distinguishes spiders.
Many graph polynomials may be derived from the coefficients of the chromatic symmetric function X
G ${X}_{G}$ of a graph G $G$ when expressed in different bases. For instance, the chromatic ...polynomial is obtained by mapping p
n
→
x ${p}_{n}\to x$ for each n $n$ in this function, while a polynomial whose coefficients enumerate acyclic orientations is obtained by mapping e
n
→
x ${e}_{n}\to x$ for each n $n$. In this paper, we study a new polynomial we call the tree polynomial arising by mapping X
P
n
→
x ${X}_{{P}_{n}}\to x$, where X
P
n ${X}_{{P}_{n}}$ is the chromatic symmetric function of a path with n $n$ vertices. In particular, we show that this polynomial has a deletion‐contraction relation and has properties closely related to the chromatic polynomial while having coefficients that enumerate certain spanning trees and edge cutsets.
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.
PDF
