Dominating Sets and Domination Polynomials of Graphs
This thesis introduces domination polynomial of a graph. The domination polynomial of a graph G of order n is the polynomial D(G; x) = Pn i=°(G) d(G; i)xi, where d(G; i) is the number of dominating sets of G of size i, and °(G) is the domination number of G. We obtain some properties of this pol...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
2009
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/7250/ http://psasir.upm.edu.my/id/eprint/7250/1/IPM_2009_7a.pdf |
| _version_ | 1848840543368380416 |
|---|---|
| author | Alikhani, Saeid |
| author_facet | Alikhani, Saeid |
| author_sort | Alikhani, Saeid |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | This thesis introduces domination polynomial of a graph. The domination polynomial of a graph G of order n is the polynomial D(G; x) =
Pn
i=°(G) d(G; i)xi,
where d(G; i) is the number of dominating sets of G of size i, and °(G) is the
domination number of G. We obtain some properties of this polynomial, and
establish some relationships between the domination polynomial of a graph G
and geometrical properties of G.
Since the problem of determining the dominating sets and the number of
dominating sets of an arbitrary graph has been shown to be NP-complete,
we study the domination polynomials of classes of graphs with specific construction. We introduce graphs with specific structure and study the construction of the family of all their dominating sets. As a main consequence,
the relationship between the domination polynomials of graphs containing a
simple path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by a shorter path is, D(G; x) = x
h
D(G¤e1; x)+D(G¤e1 ¤e2; x)+D(G¤e1 ¤e2 ¤e3; x)
i, where G¤e is the graph
obtained from G by contracting the edge e, and e1; e2 and e3 are three edges of
the path. As an example of graphs which contain no simple path of length at
least three, we study the family of dominating sets and the domination polynomials of centipedes. We extend the result of the domination polynomial of
centipedes to the graphs G ± K1, where G ± K1 is the corona of the graph G
and the complete graph K1.
As is the case with other graph polynomials, such as the chromatic polynomials
and the independence polynomials, it is natural to investigate the roots of
domination polynomial. In this thesis we study the roots of the domination
polynomial of certain graphs and we characterize graphs with one, two and
three distinct domination roots.
Two non-isomorphic graphs may have the same domination polynomial. We say
that two graphs G and H are dominating equivalence (or simply D-equivalence)
if D(G; x) = D(H; x). We study the D-equivalence classes of some graphs. We
end the thesis by proposing some conjectures and some questions related to
this polynomial. |
| first_indexed | 2025-11-15T07:29:01Z |
| format | Thesis |
| id | upm-7250 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-15T07:29:01Z |
| publishDate | 2009 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-72502013-05-27T07:34:21Z http://psasir.upm.edu.my/id/eprint/7250/ Dominating Sets and Domination Polynomials of Graphs Alikhani, Saeid This thesis introduces domination polynomial of a graph. The domination polynomial of a graph G of order n is the polynomial D(G; x) = Pn i=°(G) d(G; i)xi, where d(G; i) is the number of dominating sets of G of size i, and °(G) is the domination number of G. We obtain some properties of this polynomial, and establish some relationships between the domination polynomial of a graph G and geometrical properties of G. Since the problem of determining the dominating sets and the number of dominating sets of an arbitrary graph has been shown to be NP-complete, we study the domination polynomials of classes of graphs with specific construction. We introduce graphs with specific structure and study the construction of the family of all their dominating sets. As a main consequence, the relationship between the domination polynomials of graphs containing a simple path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by a shorter path is, D(G; x) = x h D(G¤e1; x)+D(G¤e1 ¤e2; x)+D(G¤e1 ¤e2 ¤e3; x) i, where G¤e is the graph obtained from G by contracting the edge e, and e1; e2 and e3 are three edges of the path. As an example of graphs which contain no simple path of length at least three, we study the family of dominating sets and the domination polynomials of centipedes. We extend the result of the domination polynomial of centipedes to the graphs G ± K1, where G ± K1 is the corona of the graph G and the complete graph K1. As is the case with other graph polynomials, such as the chromatic polynomials and the independence polynomials, it is natural to investigate the roots of domination polynomial. In this thesis we study the roots of the domination polynomial of certain graphs and we characterize graphs with one, two and three distinct domination roots. Two non-isomorphic graphs may have the same domination polynomial. We say that two graphs G and H are dominating equivalence (or simply D-equivalence) if D(G; x) = D(H; x). We study the D-equivalence classes of some graphs. We end the thesis by proposing some conjectures and some questions related to this polynomial. 2009 Thesis NonPeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/7250/1/IPM_2009_7a.pdf Alikhani, Saeid (2009) Dominating Sets and Domination Polynomials of Graphs. PhD thesis, Universiti Putra Malaysia. Geometrical drawing English |
| spellingShingle | Geometrical drawing Alikhani, Saeid Dominating Sets and Domination Polynomials of Graphs |
| title | Dominating Sets and Domination Polynomials of Graphs |
| title_full | Dominating Sets and Domination Polynomials of Graphs |
| title_fullStr | Dominating Sets and Domination Polynomials of Graphs |
| title_full_unstemmed | Dominating Sets and Domination Polynomials of Graphs |
| title_short | Dominating Sets and Domination Polynomials of Graphs |
| title_sort | dominating sets and domination polynomials of graphs |
| topic | Geometrical drawing |
| url | http://psasir.upm.edu.my/id/eprint/7250/ http://psasir.upm.edu.my/id/eprint/7250/1/IPM_2009_7a.pdf |