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

Elif Saygı

doi:10.19113/sdufbed.05851

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

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.

Details

Primary Language

Turkish

Subjects

-

Journal Section

-

Authors

Elif Saygı

Publication Date

August 11, 2017

Submission Date

November 23, 2016

Acceptance Date

-

Published in Issue

Year 2017 Volume: 21 Number: 3

DOI

https://doi.org/10.19113/sdufbed.05851

IZ

https://izlik.org/JA95YG37CS

Cite

RIS / Bibtex

APA

Saygı, E. (2017). Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 21(3), 782-785. https://doi.org/10.19113/sdufbed.05851

AMA

1.Saygı E. Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. J. Nat. Appl. Sci. 2017;21(3):782-785. doi:10.19113/sdufbed.05851

Chicago

Saygı, Elif. 2017. “Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes”. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21 (3): 782-85. https://doi.org/10.19113/sdufbed.05851.

EndNote

Saygı E (December 1, 2017) Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21 3 782–785.

IEEE

[1]E. Saygı, “Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes”, J. Nat. Appl. Sci., vol. 21, no. 3, pp. 782–785, Dec. 2017, doi: 10.19113/sdufbed.05851.

ISNAD

Saygı, Elif. “Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes”. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21/3 (December 1, 2017): 782-785. https://doi.org/10.19113/sdufbed.05851.

JAMA

1.Saygı E. Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. J. Nat. Appl. Sci. 2017;21:782–785.

MLA

Saygı, Elif. “Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes”. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, vol. 21, no. 3, Dec. 2017, pp. 782-5, doi:10.19113/sdufbed.05851.

Vancouver

1.Elif Saygı. Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. J. Nat. Appl. Sci. 2017 Dec. 1;21(3):782-5. doi:10.19113/sdufbed.05851