MORE ON TOTAL DOMINATION POLYNOMIAL AND Dt-EQUIVALENCE CLASSES OF SOME GRAPHS

Document Type : Original Manuscript

Authors

Department of Mathematical sciences, Yazd university, P.O. Box 89195-741, Yazd, Iran.

Abstract

Let G=(V,E) be a simple graph of order n. A total dominating set of G is a subset D of V such that every vertex of V is adjacent to some vertices of D. The total domination number of G is equal to the minimum cardinality of a total dominating set in G and is denoted by γt(G). The total domination polynomial of G is the polynomial Dt(G,x)=∑i=γt(G)ndt(G,i)xi, where dt(G,i) is the number of total dominating sets of G of size i. Two graphs G and H are said to be total dominating equivalent or simply Dt-equivalent, if Dt(G,x)=Dt(H,x). The equivalence class of G, denoted [G], is the set of all graphs Dt-equivalent to G. A polynomial ∑k=0nakxk is called unimodal if the sequence of its coefficients is unimodal, that means there is some k∈{0,1,…,n}, such that a0≤…≤ak−1≤ak≥ak+1≥…≥an. In this paper, we investigate Dt-equivalence classes of some graphs. Also, we introduce some families of graphs whose total domination polynomials are unimodal. The Dt-equivalence classes of graphs of order ≤6 are presented in the appendix.

Keywords

References

  1. S. Akbari, S. Alikhani and Y. H. Peng, Characterization of graphs using domination polynomials, European J. Combin., 31 (2010), 1714–1724.
  1. S. Alikhani, J. I. Brown and S. Jahari, On the domination polynomials of friendship graphs, Filomat, 30(1) (2016), 169–178.
  1. S. Alikhani and N. Jafari, On the roots of total domination polynomial of graphs, II, Facta Univ. Ser. Math. Inform., 34(4) (2019), 659–669.
  1. S. Alikhani and F. Jafari, On the unimodality of independence polynomial of certainclasses of graphs, Trans. Comb., 2(3) (2013), 33–41.
  1. S. Alikhani and S. Jahari, Some families of graphs whose domination polynomials are unimodal, Iran. J. Math. Sci. Inform., 12(1) (2014), 69–80.
  1. S. Alikhani and N. Jafari, Some new results on the total domination polynomial of a graph, Ars Combin., 149 (2020), 185–197.
  1. S. Alikhani and N. Jafari, Total domination polynomial of graphs from primary subgraphs,
  2. Algebr. Syst., 5(2) (2017), 127–138.
  3. S. Alikhani and Y. H. Peng, An atlas of domination polynomials of graphs of order at most six, https://arxiv.org/abs/1401.3141.
  1. S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, Ars Combin., 114 (2014), 257–266.
  1. I. Beaton and J. I. Brown, On the Unimodality of Domination Polynomials, Graphs Combin., 38(3) (2022), 90.
  1. F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: An update, Contemp. Math., 178 (1994), 417–441.
  1. F. Brenti, Unimodal, log-concave, and Polya frequency sequences in combinatorics, Mem. Amer. Math. Soc., 413, 1989.
  1. A. Burcroff and G. OB́rien, Unimodality and monotonic portions of certain domination polynomials, Discrete Math., 346(6) (2023), Article ID: 113508.
  1. L. Comtet, Advanced Combinatorics, Reidel, Boston, 1974.
  2. M. Dod, The total domination polynomial and its generalization, Congr. Numer., 219 (2014), 207–226.
  1. F. M. Dong, K. M. Koh and K. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing Co. Pte. Ltd., 2005.
  1. P. Erdös, A. Rényi and V.T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar., 1 (1966), 215–235.
  1. R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math., 4 (1970), 322–324.
  1. C. D. Godsil and B. D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc., 18 (1978), 21–28.
  1. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
  2. F. Harary, On the group of the composition of two graphs, Duke Math. J., 26 (1959), 29–36.
Journal of Algebraic Systems
Volume 13, Issue 2
July 2025
Pages 77-94

Files

Share

How to cite

Statistics