Fibonacci Küplerinin Baskınlık ve Toplam Baskınlık Sayıları için Üst Sınırlar

Baglantı ağları için en temel modellerden birin-boyutlu hiperküp grafı Qn dir ve Qn nin köşeleri boyu n olan tüm ikilik diziler ile temsil edilir. n-boyutlu Fibonacci küpü Γn, Qn nin bir alt grafıdır ve köşeleri, ikilik dizi gösterimlerinde ardışık 1 içermeyen tüm köşelere karşı gelir. Bu çalışmada, Fibonacci küplerinin baskınlık ve toplam baskınlık sayıları ile ilgilendik. Öncelikle, n ≥ 13 olmak üzere Γn nin baskınlık sayısı için üst sınırlar elde ettik. Sonrasında bu sonuçları kullanarak n ≥ 14 olmak üzere Γn nin toplam baskınlık sayısı için üst sınırlar bulduk ve bu sınırların [1] de verilen üst sınırları geliştirdiginiğördük.

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

One of the basic model for interconnection networks is the n-dimensional hypercube graph Qn and the vertices of Qn are represented by all binary strings of length n. The Fibonacci cube Γn of dimension n is a subgraph of Qn, 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 Γn for n ≥ 13. Then using these result we obtain upper bounds on the total domination number of Γn for n ≥ 14 and we see that these upper bounds improve the bounds given in [1].

PDF

___

Klavžar, S., Mollard, M., Petkovšek, M. 2011. The degree sequence of Fibonacci and Lucas cubes. Discrete Mathematics, 311 (2011), 1310-1322.
Payan, C. 1975. Sur le nombre d’absorption d’un graphe simple. Cahiers du Centre d’Etudes de Recherche Operationelle, 17 (1975) 307-317.
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.
Vajda S. 1989. Fibonacci and Lucas numbers and the golden section. Halsted Press, New York (1989).
Ilic, A., Miloševi ´ c, M. 2017. The parameters of ´ Fibonacci and Lucas cubes. Ars Mathematica Contemporanea, 12 (2017) 25-29.
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.
Pike, D. A., Zou, Y. 2012. The domination number of Fibonacci cubes. Journal of Combinatorial Mathematics and Combinatorial Computing, 80 (2012), 433- 444.
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.
Vesel, A. 2015. Linear recognition and embedding of Fibonacci cubes. Algorithmica 71(4) (2015), 1021- 1034.
Klavžar, S., Mollard, M. 2014. Asymptotic properties of Fibonacci cubes and Lucas cubes. Annals of Combinatorics, 18(3) (2014), 447-457.
Saygı, E., Egecio ğlu, Ö. 2016. q-cube enumerator polynomial of Fibonacci cubes. Discrete Applied Mathematics, 226 (2017), 127-137.
Mollard, M. 2017. Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes. Discrete Applied Mathematics, 219 (2017), 219-221.
Saygı, E., Egecio ˘ glu, Ö. 2016. Counting disjoint hy- ˘ percubes in Fibonacci cubes. Discrete Applied Mathematics, 215 (2016), 231-237.
Gravier, S., Mollard, M., Špacapan, S., Zemljic, S.S. ˇ 2015. On disjoint hypercubes in Fibonacci cubes. Discrete Applied Mathematics, 190-191 (2015), 50-55.
Klavžar, S., Mollard, M. 2012. Cube polynomial of Fibonacci and Lucas cube. Acta Applicandae Mathematicae, 117 (2012), 93-105.
Klavžar, S. 2013. Structure of Fibonacci cubes: a survey. Journal of Combinatorial Optimization, 25 (2013), 505-522.
Hsu, W.-J. 1993. Fibonacci cubes–a new interconnection technology. Transactions on Parallel and Distributed Systems, 4(1) (1993), 3-12.
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).