Dominating sets and domination polynomials of certain graphs, II

• Autorzy: Alikhani S. , Yee-hock P.
• Języki publikacji: EN

Abstrakty

EN

The domination polynomial of a graph G of order n is the polynomial [formula] where d(G, i) is the number of dominating sets of G of size i, and ϒ (G) is the domination number of G. In this paper, we obtain some properties of the coefficients of D(G, x). Also, by study of the dominating sets and the domination polynomials of specific graphs denoted by G'(m), we obtain a relationship between the domination polynomial of graphs containing an induced path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by shorter path. As examples of graphs G' (m), we study the dominating sets and domination polynomials of cycles and generalized theta graphs. Finally, we show that, if n ≡ 0, 2(mod 3) and D(G, x) = D(Cn, x), then G = Cn.

Słowa kluczowe

EN

domination polynomial; dominating set; cycle; theta graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2010
• Tom: Vol. 30, no. 1
• Strony: 37--51
• Opis fizyczny: Bibliogr. 10 poz. rys., tab.

Twórcy

autor

Alikhani S.

autor

Yee-hock P.

• Yazd University Department of Mathematics 89195-741 Yazd, Iran,

Bibliografia

• [1] S. Akbari, S. Alikhani, Y.H. Peng, Characterization of graphs using Domination Polynomial , submitted.
• [2] S. Akbari, M.R. Oboudi, Cycles are determined by by their domination polynomials, Ars Combin., to appear.
• [3] S. Alikhani, Dominating Sets and Domination Polynomials of Graphs, Ph.D. Thesis, University Putra Malaysia, March 2009.
• [4] S. Alikhani, Y.H. Peng, Introduction to Domination Polynomial of a Graph, Ars Combin., to appear.
• [5] S. Alikhani, Y.H. Peng, Dominating sets and domination polynomial of cycles, Global Journal of Pure and Applied Mathematics 4 (2008) 2, 151–162.
• [6] S. Alikhani, Y.H. Peng, Dominating Sets and Domination Polynomial of Certain Graphs, submitted.
• [7] J.A. Bondy, U.S.R. Murty, Graph theory with applications, Elsevier Science Publishing, 6th ed., 1984.
• [8] Gray Chartrand, Ping Zhang, Introduction to Graph Theory, McGraw Hill, Higher Education, 2005.
• [9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, NewYork, 1998.
• [10] P. van’t Hof, D. Paulusma, A new characterization of P6-free graphs, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.08.025.