Geodesic
Recurrence relations and splitting formulas for the domination polynomial
Tomer Kotek1 ; James Preen2 ; Frank Simon3 ; Peter Tittmann3 ; Martin Trinks3
1Technion - Israel Institute of Technology Haifa, Israel
2Mathematics Cape Breton University Sydney, NS B1P6L2, Canada
3Faculty Mathematics / Sciences / Computer Sciences Hochschule Mittweida - University of Applied Sciences Mittweida, Germany
The electronic journal of combinatorics, Tome 19 (2012) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2475
Classification : 05C69, 05C31
Mots-clés : domination polynomial, recurrence relation, splitting formula

Tomer Kotek  1   ; James Preen  2   ; Frank Simon  3   ; Peter Tittmann  3   ; Martin Trinks  3

1 Technion - Israel Institute of Technology Haifa, Israel
2 Mathematics Cape Breton University Sydney, NS B1P6L2, Canada
3 Faculty Mathematics / Sciences / Computer Sciences Hochschule Mittweida - University of Applied Sciences Mittweida, Germany 
@article{10_37236_2475,
     author = {Tomer Kotek and James Preen and Frank Simon and Peter Tittmann and Martin Trinks},
     title = {Recurrence relations and splitting formulas for the domination polynomial},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {3},
     doi = {10.37236/2475},
     zbl = {1252.05164},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2475/}
}
TY  - JOUR
AU  - Tomer Kotek
AU  - James Preen
AU  - Frank Simon
AU  - Peter Tittmann
AU  - Martin Trinks
TI  - Recurrence relations and splitting formulas for the domination polynomial
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2475/
DO  - 10.37236/2475
ID  - 10_37236_2475
ER  - 
%0 Journal Article
%A Tomer Kotek
%A James Preen
%A Frank Simon
%A Peter Tittmann
%A Martin Trinks
%T Recurrence relations and splitting formulas for the domination polynomial
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2475/
%R 10.37236/2475
%F 10_37236_2475
Tomer Kotek; James Preen; Frank Simon; Peter Tittmann; Martin Trinks. Recurrence relations and splitting formulas for the domination polynomial. The electronic journal of combinatorics, Tome 19 (2012) no. 3. doi: 10.37236/2475

Cité par Sources :