ترغب بنشر مسار تعليمي؟ اضغط هنا

Subset-Sum Representations of Domination Polynomials

71   0   0.0 ( 0 )
 نشر من قبل Peter Tittmann
 تاريخ النشر 2012
  مجال البحث
والبحث باللغة English




اسأل 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.
68 - Zhengjun Cao , Lihua Liu 2016
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$.
101 - Peter Ulrickson 2021
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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا