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

Articles in Press

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 $\gamma_t(G)$. The total domination polynomial of $G$ is the polynomial $D_t(G,x)=\sum_{i=\gamma_t(G)}^n d_t(G,i)x^i$, where $d_t(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 $\mathcal{D}_t$-equivalent, if $D_t(G,x)=D_t(H,x)$. The equivalence class of $G$, denoted $[G]$, is the set of all graphs $\mathcal{D}_t$-equivalent to $G$. A polynomial $\sum_{k=0}^n a_kx^k$ is called unimodal if the sequence of its coefficients is unimodal, that means there is some $k \in \{0, 1, \ldots , n\}$, such that $a_0 \leq \ldots \leq a_{k-1} \leq a_k\geq a_{k+1} \geq \ldots \geq a_n$. In this paper, we investigate $\mathcal{D}_t$-equivalence classes of some graphs. Also, we introduce some families of graphs whose total domination polynomials are unimodal. The $\mathcal{D}_t$-equivalence classes of graphs of order $\leq 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

Articles in Press, Accepted Manuscript
Available Online from 09 April 2024

Files

Share

How to cite

Statistics