Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecurrence relations and splitting formulas for the domination polynomial
286
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We introduce a new bivariate polynomial ${displaystyle J(G; x,y):=sumlimits_{W in V(G)} x^{|W|}y^{|N(W)|}}$ which contains the standard domination polynomial of the graph $G$ in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.
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.
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.
In combinatorics, a latin square is a $ntimes n$ matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Associated to each latin square, we can define a simple graph called a latin square graph. In this article, we compute lower and upper bounds for the domination number and the k-tuple total domination numbers of such graphs. Moreover, we describe a formula for the 2-tuple total domination number.
The operator nabla, introduced by Garsia and the author, plays a crucial role in many aspect of the study of diagonal harmonics. Besides giving several new formulas involving this operator, we show how one is lead to representation theoretic explanations for conjectures about the effect of this operator on Schur functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
