On the chromatic polynomial and the domination number of k-Fibonacci cubes

Egeciouglu O., Saygı E., Saygı Z.

TURKISH JOURNAL OF MATHEMATICS, cilt.44, sa.5, ss.1813-1823, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 44 Sayı: 5
  • Basım Tarihi: 2020
  • Doi Numarası: 10.3906/mat-2004-20
  • Dergi Adı: TURKISH JOURNAL OF MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, MathSciNet, zbMATH, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.1813-1823
  • Hacettepe Üniversitesi Adresli: Evet

Özet

Fibonacci cubes are defined as subgraphs of hypercubes, where the vertices are those without two consecutive l's in their binary string representation. k-Fibonacci cubes are in turn special subgraphs of Fibonacci cubes obtained by eliminating certain edges. This elimination is carried out at the step analogous to where the fundamental recursion is used to construct Fibonacci cubes themselves from the two previous cubes by link edges. In this work, we calculate the vertex chromatic polynomial of k-Fibonacci cubes for k = 1,2. We also determine the domination number and the total domination number of k-Fibonacci cubes for n, k <= 12 by using an integer programming formulation.