Domination polynomial of~clique~cover~product~of~graphs

Somayeh Jahari ; Saeid Alikhani

Algebra and discrete mathematics, Tome 28 (2019) no. 2, pp. 248-259.

Résumé

Let $G$ be a simple graph of order $n$. We prove that the domination polynomial of the clique cover product $G^\mathcal{C} \star H^{V(H)}$ is $$ D(G^\mathcal{C} \star H,x) =\prod_{i=1}^k\Big[\big((1+x)^{n_i}-1\big)(1+x)^{|V(H)|}+D(H,x)\Big], $$ where each clique $C_i \in \mathcal{C}$ has $n_i$ vertices. As an application, we study the $\mathcal{D}$-equivalence classes of some families of graphs and, in particular, describe completely the $\mathcal{D}$-equivalence classes of friendship graphs constructed by coalescing $n$ copies of a cycle graph of length $3$ with a common vertex.

Détail

Keywords: $\mathcal{D}$-equivalence class, friendship graphs.
Mots-clés : domination polynomial, clique cover

Bibliographie

[1] G. Aalipour-Hafshejani, S. Akbari and Z. Ebrahimi, “On $\mathcal{D}$-equivalence class of complete bipartite graphs”, Ars Comb., 117 (2014), 275–288 | MR | Zbl

[2] S. Akbari, S. Alikhani and Y. H. Peng, “Characterization of graphs using domination polynomial”, European J. Combin., 31:7 (2010), 1714–1724 | DOI | MR | Zbl

[3] S. Alikhani and Y. H. Peng, “Domination polynomials of cubic graphs of order $10$”, Turk. J. Math., 35:3 (2011), 355–366 | MR | Zbl

[4] S. Alikhani, “On the domination polynomial of some graph operations”, ISRN Comb., 2013 (2013), 146595, 3 pp. | MR | Zbl

[5] S. Alikhani and Y. H. Peng, “Introduction to domination polynomial of a graph”, Ars Comb., 114 (2014), 257–266 | MR | Zbl

[6] S. Alikhani, J. I. Brown, and S. Jahari, “On the domination polynomials of friendship graphs”, Filomat, 30:1 (2016), 169–178 | DOI | MR | Zbl

[7] B. M. Anthony and M. E. Picollelli, “Complete $r$-partite graphs determined by their domination polynomial”, Graphs Combin., 31:6 (2015), 1993–2002 | DOI | MR | Zbl

[8] L. W. Beineke and R. E. Pippert, “The number of labeled $k$-dimensional trees”, J. Comb. Theory, 6 (1969), 200–205 | DOI | MR | Zbl

[9] F. M. Dong, K. M. Koh and K. L. Teo, Chromatic polynomials and chromaticity of graphs, World Scientific Publishing, 2005 | MR | Zbl

[10] 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 | MR | Zbl

[11] R. Frucht and F. Harary, “On the corona of two graphs”, Aequationes Math., 4:3 (1970), 322–325 | DOI | MR | Zbl

[12] M. R. Garey and D. S. Johnson, A Guide to the Theory of NP-Completeness, WH Freemann, New York, 1979 | MR | Zbl

[13] F. Harary and E. M. Palmer, “On acyclic simplicial complexes”, Mathematika, 15 (1968), 115–122 | DOI | MR | Zbl

[14] S. Jahari and S. Alikhani, “Domination polynomials of $k$-tree related graphs”, Int. J. Comb., 2014 (2014), 390170, 5 pp. | MR | Zbl

[15] S. Jahari and S. Alikhani, “On $\mathcal{D}$-equivalence classes of some graphs”, Bull. Georg. Nat. Acad. Sci., 10:1 (2016), 9–16 | MR

[16] T. Kotek, J. Preen, F. Simon, P. Tittmann and M. Trinks, “Recurrence relations and splitting formulas for the domination polynomial”, Electron. J. Combin., 19:3 (2012), 27 pp. | DOI | MR | Zbl

[17] V. E. Levit and E. Mandrescu, “A family of graphs whose independence polynomials are both palindromic and unimodal”, Carpathian J. Math., 23:1–2 (2007), 108–116 | MR | Zbl

[18] X. Li and I. Gutman, “A unified approach to the first derivatives of graph polynomials”, Discrete Appl. Math., 58:3 (1995), 293–297 | DOI | MR | Zbl

[19] D. Stevanović, “Graphs with palindromic independence polynomial”, New York Graph Theory Day., 34 (1997), 31–36 | MR

[20] M. Walsh, “The hub number of a graph”, Int. J. Math. Comput. Sci., 1:1 (2006), 117–124 | MR | Zbl

[21] B. X. Zhu, “Clique cover products and unimodality of independence polynomials”, Discrete Appl. Math., 206 (2016), 172–180 | DOI | MR | Zbl