Dominating Sets and Domination Polynomials of Stars

Kahat, Sahib Shayyal; Khalaf, Abdul Jalil M.; Hasni, Roslan
June 2014
Australian Journal of Basic & Applied Sciences;Jun2014, Vol. 8 Issue 9, p383
Academic Journal
Let G = (V, E)be a simple graph. A setD ⊆ V is a dominating set of G, if every vertex in V - Dis adjacent to at least one vertex in D. Let Sn be star graph with order n. Let Sni be the family of dominating sets of a star Snwith cardinality i, and let d(Sn, i )= /Sni/. Results. In this paper, we construct Sn, and obtain a recursive formula for d(Sn,i). Conclusion. Using this recursive formula, we consider the polynomial D(Sn, x) =∑i=12=1d(Sn)xi, which we call domination polynomial of star graphs and obtain some properties of this polynomial.


Related Articles

  • Tutte Polynomial of Generalized Flower Graphs. Narayana, Nithya Sai // International Journal of Mathematical Combinatorics;2016, Vol. 2, p29 

    The book graph denoted by Bn,2 is the Cartesian Product Sn+1 x P2 where Sn+1 is a star graph with n vertices of degree 1 and one vertex of degree n and P2 is the path graph of 2 vertices. Let Xn, p denote the generalized form of Book graph where a family of p cycles which are n in number, is...

  • Terminal hosoya polynomial of thorn graphs. Narayankar, K. P.; Lokesh, S. B.; Shirkol, S. S.; Ramane, H. S. // Scientia Magna;2013, Vol. 9 Issue 3, p37 

    The terminal Hosoya polynomial of thorn graphs is described. Also the terminal Hosoya polynomial for caterpillars, thorn stars, and thorn rings are obtained.

  • Dominator Coloring on Star and Double Star Graph Families. Kavitha, K.; David, N.G. // International Journal of Computer Applications;6/15/2012, Vol. 48, p22 

    Dominator chromatic number of central, middle and total graphs of star and double star graph families are found in this paper. Also the relationship between dominator chromatic number and star chromatic number of the above graph families are obtained.

  • A Note on the b-Chromatic Number of Corona of Graphs. LISNA, P. C.; SUNITHA, M. S. // Journal of Interconnection Networks;2015, Vol. 15 Issue 1/2, p-1 

    A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph G, denoted by , is the maximal integer k such that G has a b-coloring with k...

  • RT-Symmetric Laplace Operators on Star Graphs: Real Spectrum and Self-Adjointness. Astudillo, Maria; Kurasov, Pavel; Usman, Muhammad // Advances in Mathematical Physics;12/27/2015, p1 

    How ideas of PT-symmetric quantum mechanics can be applied to quantum graphs is analyzed, in particular to the star graph. The class of rotationally symmetric vertex conditions is analyzed. It is shown that all such conditions can effectively be described by circulant matrices: real in the case...

  • Retracted: An Inverse Spectral Problem for the Sturm-Liouville Operator on a Three-Star Graph.  // ISRN Otolaryngology;2014, p1 

    No abstract available.

  • Regularly Varying Solutions of Second-Order Difference Equations with Arbitrary Sign Coefficient. Matucci, Serena; Řehák, Pavel // Advances in Difference Equations;2010, Special section p1 

    No abstract available.

  • TOTAL DOMINATION POLYNOMIALS OF SQUARE OF SOME GRAPHS. M. P., Shyama; V., Anil Kumar // Advances & Applications in Discrete Mathematics;Apr2015, Vol. 15 Issue 2, p167 

    In this paper, we study the total domination number and total domination polynomial of square of some graphs. We also discuss nonzero real total domination roots, the roots of total domination polynomials, of some of these graphs.

  • A New Bound on the Total Domination Subdivision Number. Favaron, O.; Karami, H.; Khoeilar, R.; Sheikholeslami, S. M. // Graphs & Combinatorics;May2009, Vol. 25 Issue 1, p41 

    A set S of vertices of a graph G = ( V, E) without isolated vertex is a total dominating set if every vertex of V( G) is adjacent to some vertex in S. The total domination number γ t( G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics