Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes

Year 2017, Volume: 21 Issue: 3, 782 - 785, 11.08.2017

Elif Saygı

Abstract

One of the basic model for interconnection networks is the $n$-dimensional hypercube graph $Q_n$ and the vertices of $Q_n$ are represented by all binary strings of length $n$. The Fibonacci cube $\Gamma_n$ of dimension $n$ is a subgraph of $Q_n$, where the vertices correspond to those without two consecutive 1s in their string representation. In this paper, we deal with the domination number and the total domination number of Fibonacci cubes. First we obtain upper bounds on the domination number of $\Gamma_n$ for $n\ge 13$. Then using these result we obtain upper bounds on the total domination number of $\Gamma_n$ for $n\ge 14$ and we see that these upper bounds improve the bounds given in [1].

Keywords

Fibonacci cube, Domination number; Total domination number

References

• [1] Azarija, J., Klavžar, S., Rho, Y., Sim, S. 2016. On domination-type invariants of Fibonacci cubes and hypercubes. http://www.fmf.unilj.si/ klavzar/preprints/Total-dom-cubes-submit.pdf (Date of access: 20.07.2017).
• [2] Hsu, W.-J. 1993. Fibonacci cubes–a new interconnection technology. Transactions on Parallel and Distributed Systems, 4(1) (1993), 3-12.
• [3] Klavžar, S. 2013. Structure of Fibonacci cubes: a survey. Journal of Combinatorial Optimization, 25 (2013), 505-522.
• [4] Klavžar, S., Mollard, M. 2012. Cube polynomial of Fibonacci and Lucas cube. Acta Applicandae Mathematicae, 117 (2012), 93-105.
• [5] Gravier, S., Mollard, M., Špacapan, S., Zemljic, S.S. 2015. On disjoint hypercubes in Fibonacci cubes. Discrete Applied Mathematics, 190-191 (2015), 50-55.
• [6] Saygı, E., Eğecioğlu, Ö. 2016. Counting disjoint hypercubes in Fibonacci cubes. Discrete Applied Mathematics, 215 (2016), 231-237.
• [7] Mollard, M. 2017. Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes. Discrete Applied Mathematics, 219 (2017), 219-221.
• [8] Saygı, E., Eğecioğlu, Ö. 2016. q-cube enumerator polynomial of Fibonacci cubes. Discrete Applied Mathematics, 226 (2017), 127-137.
• [9] Klavžar, S., Mollard, M. 2014. Asymptotic properties of Fibonacci cubes and Lucas cubes. Annals of Combinatorics, 18(3) (2014), 447-457.
• [10] Vesel, A. 2015. Linear recognition and embedding of Fibonacci cubes. Algorithmica 71(4) (2015), 1021-1034.
• [11] Ashrafi, A.R., Azarija, J., Fathalikhani, K., Klavžar, S., Petkovšek, M. 2016. Vertex and Edge Orbits of Fibonacci and Lucas Cubes. Annals of Combinatorics, 20(2) (2016), 209-229.
• [12] Pike, D. A., Zou, Y. 2012. The domination number of Fibonacci cubes. Journal of Combinatorial Mathematics and Combinatorial Computing, 80 (2012), 433-444.
• [13] Castro, A., Klavžar, S., Mollard, M., Rho, Y. 2011. On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes. Computers and Mathematics with Applications, 61 (2011), 2655-2660.
• [14] Ilic, A., Miloševic, M. 2017. The parameters of Fibonacci and Lucas cubes. Ars Mathematica Contemporanea, 12 (2017) 25-29.
• [15] Vajda S. 1989. Fibonacci and Lucas numbers and the golden section. Halsted Press, New York (1989).
• [16] Arnautov, V. I. 1974. Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices (Russian). Prikl. Mat. i Programmirovanie, 11 (1974), 3-8.
• [17] Payan, C. 1975. Sur le nombre d’absorption d’un graphe simple. Cahiers du Centre d’Etudes de Recherche Operationelle, 17 (1975) 307-317.
• [18] Klavžar, S., Mollard, M., Petkovšek, M. 2011. The degree sequence of Fibonacci and Lucas cubes. Discrete Mathematics, 311 (2011), 1310-1322.