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

Öz

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].

Anahtar Kelimeler

Fibonacci cube,Domination number; Total domination number

Kaynakça

[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.

Ayrıntılar

Birincil Dil

Türkçe

Konular

-

Bölüm

-

Yazarlar

Elif Saygı

Yayımlanma Tarihi

11 Ağustos 2017

Gönderilme Tarihi

23 Kasım 2016

Kabul Tarihi

-

Yayımlandığı Sayı

Yıl 2017 Cilt: 21 Sayı: 3

DOI

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

IZ

https://izlik.org/JA95YG37CS

Kaynak Göster

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. Süleyman Demirel Üniv. Fen Bilim. Enst. Derg. 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 (01 Aralık 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”, Süleyman Demirel Üniv. Fen Bilim. Enst. Derg., c. 21, sy 3, ss. 782–785, Ara. 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 (01 Aralık 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. Süleyman Demirel Üniv. Fen Bilim. Enst. Derg. 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, c. 21, sy 3, Aralık 2017, ss. 782-5, doi:10.19113/sdufbed.05851.

Vancouver

1.Elif Saygı. Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes. Süleyman Demirel Üniv. Fen Bilim. Enst. Derg. 01 Aralık 2017;21(3):782-5. doi:10.19113/sdufbed.05851