Yıl 2017, Cilt 21, Sayı 3, Sayfalar 782 - 785 2017-08-11

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

Elif SAYGI [1]

622 210

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].
Fibonacci cube, Domination number; Total domination number
  • [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.
Konular
Dergi Bölümü Makaleler
Yazarlar

Yazar: Elif SAYGI

Bibtex @ { sdufenbed382218, journal = {Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi}, issn = {}, eissn = {1308-6529}, address = {Süleyman Demirel Üniversitesi}, year = {2017}, volume = {21}, pages = {782 - 785}, doi = {10.19113/sdufbed.05851}, title = {Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes}, key = {cite}, author = {SAYGI, Elif} }
APA SAYGI, 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. Retrieved from http://dergipark.gov.tr/sdufenbed/issue/34610/382218
MLA SAYGI, E . "Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes". Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21 (2017): 782-785 <http://dergipark.gov.tr/sdufenbed/issue/34610/382218>
Chicago SAYGI, E . "Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes". Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21 (2017): 782-785
RIS TY - JOUR T1 - Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes AU - Elif SAYGI Y1 - 2017 PY - 2017 N1 - DO - T2 - Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi JF - Journal JO - JOR SP - 782 EP - 785 VL - 21 IS - 3 SN - -1308-6529 M3 - UR - Y2 - 2018 ER -
EndNote %0 Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes %A Elif SAYGI %T Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes %D 2017 %J Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi %P -1308-6529 %V 21 %N 3 %R %U
ISNAD SAYGI, Elif . "Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes". Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi 21 / 3 (Ağustos 2017): 782-785.