اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRecurrence relations and splitting formulas for the domination polynomial
285
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 p
olynomial 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 sati
sfy 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 relation
s. 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 grap
h. 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 explanat
ions for conjectures about the effect of this operator on Schur functions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
