اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSubset-Sum Representations of Domination Polynomials
108
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this paper representations of D(G,x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G,x) as a sum ranging over spanning bipartite subgraphs of G. We call a graph G conformal if all of its components are of even order. We show that the number of dominating sets of G equals a sum ranging over vertex-induced conformal subgraphs of G.
قيم البحث
اقرأ أيضاً
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various pr
oducts, ranging from explicit formulae and recurrences for specific families to more general results. As an application, we show the domination polynomial is computationally hard to evaluate.
In 1990, Alon and Kleitman proposed an argument for the sum-free subset problem: every set of n nonzero elements of a finite Abelian group contains a sum-free subset A of size |A|>frac{2}{7}n. In this note, we show that the argument confused two diff
erent randomness. It applies only to the finite Abelian group G = (Z/pZ)^s where p is a prime. For the general case, the problem remains open.
Let $G$ be an additive abelian group and $Ssubset G$ a subset. Let $Sigma(S)$ denote the set of group elements which can be expressed as a sum of a nonempty subset of $S$. We say $S$ is zero-sum free if $0 otin Sigma(S)$. It was conjectured by R.B.~
Eggleton and P.~Erd{o}s in 1972 and proved by W.~Gao et. al. in 2008 that $|Sigma(S)|geq 19$ provided that $S$ is a zero-sum free subset of an abelian group $G$ with $|S|=6$. In this paper, we determined the structure of zero-sum free set $S$ where $|S|=6$ and $|Sigma(S)|=19$.
The well-known notion of domination in a graph abstracts the idea of protecting locations with guards. This paper introduces a new graph invariant, the autonomous domination number, which abstracts the idea of defending a collection of locations with
autonomous agents following a simple protocol to coordinate their defense using only local information.
We show that Nederlofs algorithm [Information Processing Letters, 118 (2017), 15-16] for constructing a proof that the number of subsets summing to a particular integer equals a claimed quantity is flawed because: 1) its consistence is not kept; 2) the proposed recurrence formula is incorrect.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
