Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that any graph polynomial from a wide class of graph polynomials yields a recurrence relation on an infinite class of families of graphs. The recurrence relations we obtain have coefficients which themselves satisfy linear recurrence relations. We give explicit applications to the Tutte polynomial and the independence polynomial. Furthermore, we get that for any sequence $a_{n}$ satisfying a linear recurrence with constant coefficients, the sub-sequence corresponding to square indices $a_{n^{2}}$ and related sub-sequences satisfy recurrences with recurrent coefficients.
rate research
Read More
Answering an open question from 2007, we construct infinite $k$-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~$k$. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us to answer general questions on behaviour of degrees in crossing-critical graphs: we show that, for any set of integers $D$ such that $min(D)geq 3$ and $3,4in D$, and for any sufficiently large $k$, there exists a $k$-crossing-critical family such that the numbers in $D$ are precisely the vertex degrees that occur arbitrarily often in (large enough) graphs of this family. Furthermore, even if both $D$ and some average degree in the interval $(3,6)$ are prescribed, $k$-crossing-critical families exist for any sufficiently large $k$.
The domination polynomial D(G,x) of a graph G is the generating function of its dominating sets. We prove that D(G,x) satisfies a wide range of reduction formulas. We show linear recurrence relations for D(G,x) for arbitrary graphs and for various special cases. We give splitting formulas for D(G,x) based on articulation vertices, and more generally, on splitting sets of vertices.
Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebraic: The complete graphs $K_n$ and the complete bipartite graphs $K_{n,n}$ can be characterized as those graphs whose matching polynomials satisfy a certain recurrence relations and are related to the Hermite and Laguerre polynomials. An encoded graph invariant: The absolute value of the chromatic polynomial $chi(G,X)$ of a graph $G$ evaluated at $-1$ counts the number of acyclic orientations of $G$. In this paper we prove a general theorem on graph families which are characterized by families of polynomials satisfying linear recurrence relations. This gives infinitely many instances similar to the characterization of $K_{n,n}$. We also show where to use, instead of the Hermite and Laguerre polynomials, linear recurrence relations where the coefficients do not depend on $n$. Finally, we discuss the distinctive power of graph polynomials in specific form.
A graph polynomial $P$ is weakly distinguishing if for almost all finite graphs $G$ there is a finite graph $H$ that is not isomorphic to $G$ with $P(G)=P(H)$. It is weakly distinguishing on a graph property $mathcal{C}$ if for almost all finite graphs $Ginmathcal{C}$ there is $H in mathcal{C}$ that is not isomorphic to $G$ with $P(G)=P(H)$. We give sufficient conditions on a graph property $mathcal{C}$ for the characteristic, clique, independence, matching, and domination and $xi$ polynomials, as well as the Tutte polynomial and its specialisations, to be weakly distinguishing on $mathcal{C}$. One such condition is to be addable and small in the sense of C. McDiarmid, A. Steger and D. Welsh (2005). Another one is to be of genus at most $k$.
We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over $mathbb Z$ or ${mathbb Z}_m$ and allow an interpretation as counting the number of relations satisfying a property expressible in Monadic Second Order Logic (MSOL). C. Blatter and E. Specker (1981) showed that if such a function $f$ counts the number of binary relations satisfying a property expressible in MSOL then $f$ satisfies for every $m in mathbb{N}$ a linear recurrence relation over $mathbb{Z}_m$. In this paper we give a complete characterization in terms of definability in MSOL of the combinatorial functions which satisfy a linear recurrence relation over $mathbb{Z}$, and discuss various extensions and limitations of the Specker-Blatter theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
