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

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

Abstract

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

Özet

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.