Dominating Sets and Domination Polynomials of Graphs

    UNIVERSITI PUTRA MALAYSIA DOMINATING SETS AND DOMINATION POLYNOMIALS OF GRAPHS             SAEID ALIKHANI T IPM 2009 7   DOMINATING SETS AND DOMINATION POLYNOMIALS OF GRAPHS By SAEID ALIKHANI Thesis Submitted to the School of Graduate Studies, Universiti Putra Malaysia in Fulfilment of the Requirements for the Degree of Doctor of Philosophy March 2009 DEDICATION To My wife and my son Elahe and Amir Hossein For their great patience My Parents For their encouragement and My Dear Teachers ii Abstract of thesis presented to the Senate of Universiti Putra Malaysia in fulfillment of the requirement for the degree of Philosophy of Doctor DOMINATING SETS AND DOMINATION POLYNOMIALS OF GRAPHS By SAEID ALIKHANI March 2009 Chair: Prof. Dr. Peng Yee Hock, PhD Faculty: Institute for Mathematical Research This thesis introduces domination polynomial of a graph. The domination polynomial of a graph G of order n is the polynomial D(G, x) = n 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) = iii x D(G * e1 , x) + D(G * e1 * e2 , x) + D(G * e1 * e2 * e3 , x) , 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 o K1 , where G o 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. iv Abstrak tesis yang dikemukakan kepada Senat Universiti Putra Malaysia sebagai memenuhi keperluan untuk ijazah Doktor Falsafah SET DOMINASI DAN POLINOMIAL DOMINASI BAGI GRAF Oleh SAEID ALIKHANI Mac 2009 Pengerusi: Prof. Dr. Peng Yee Hock, PhD Fakulti: Institut Penyelidikan Matematik Tesis ini perkenalkan polinomial dominasi bagi satu graf. Polinomial dominasi bagi suatu graf G berperingkat n ialah polynomial D(G, x) = n i=? (G) d(G, i)xi , dimana d(G, i) ialah bilangan set dominasi bagi G yang bersaiz i, dan ? (G) ialah nombor dominasi bagi G. Kita perolehi beberapa sifat polinomial ini, dan beberapa hubungan di antara polinomial dominasi suatu graf G dan sifat geometri daripada G. Oleh sebab masalah menentukan set dominasi dan bilangan set dominasi bagi sebarang graf adalah diketahui NP-lengkap, kita kaji polinomial dominasi bagi kelas-kelas graf dengan pembinaan tertentu. Kita perkenalkan graf dengan struktur tertentu dan mengkaji pembinaan famili semua set dominasinya. Sebagai akibat utama, hububgan antara polinomial dominasi graf yang mengandungi satu lintasan ringkas panjang sekurang-kurangnya tiga, dan polinomial dominasi graf berkaitan yang diperolehi dengan menggantikan lintasan itu dengan lintasan lebih pendek ialah D(G, x) = x D(G * e1 , x) + D(G * e1 * e2 , x) + D(G * e1 * e2 * e3 , x) , dimana G * e ialah graf yang diperolehi daripada G dengan v mengecutkan garis e, dan e1 , e2 dan e3 adalah tiga garis dalam lintasan tersebut. Sebagai contoh graf yang tidak mengandungi lintasan ringkas panjang sekurang-kurangnya tiga pula, kita kaji famili set dominasi dan polinomial dominasi bagi "centipede". Kita perluaskan keputusan mengenai polinomial dominasi centipedes kepada graph G o K1 , dimana G o K1 ialah corona graf G dan graf lengkap K1 . Sebagaimana dengan polinomial graf lain, seperti polinomial kromatik dan polinomial takbersandar, mengkaji punca polinomial dominasi adalah lazim. Dalam tesis ini, kita kaji punca polinomial dominasi bagi graf tertentu dan kita cirikan graf-graf dengan satu, dua dan tiga punca dominasi berbeza. Dua graf tak isomorfik mungkin menpunyai polinomial dominasi yang sama. Kita kata dua graf G dan H adalah setara dominasi (atau D-setara) jika D(G, x) = D(H, x). Kita mengkaji kelas D-setara bagi beberapa graf. Kita juga mencadangkan konjektur dan menggariskan beberapa soalan yang berkaitan dengan polinomial ini. vi ACKNOWLEDGEMENTS First and foremost, all praise to the almighty ALLAH for His blessings and merciful that enable me to learn. This thesis is the result of almost three years of work where I have been accompanied by some people. I now have the pleasant opportunity to express my gratitude to all of them. I am sincerely grateful to my supervisor, Prof. Dr. Yee-hock Peng, for giving me the opportunity to work under his supervision, for his genuine interest in my research and ...