The κ-tuple Domination Number And Particular Cycles Of De Bruijn And Kautz Graphs

Advances in technology, especially the advent of VLSI circuit technology, have made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. One crucial step on designing a large-scale parallel and distributed system is to determine the topology of the interconnection network (network for short). The network topology not only affects the hardware architecture but also the nature of the system software that can be used in a parallel and distributed system. The de Bruijn and Kautz graphs are two of the most popular interconnection networks.For various considerations, it is expected to control the entire network system by a certain number of processors. In recent years, many people focus on the study of the domination problem of undirected graphs. In a graph G, we say a vertex dominate its neighbors and itself. For an integerκ≥1, aκ-tuple domination set D is a set of vertices such that each vertex of G is dominated byκvertices in D. Theκ-tuple domination number is the order of the minimumκ-tuple domination set, denoted byγκ(G).Because the structures of the cycles are used to model stability in parallel processing, we also choose the cycle to study in graphs. The converse of a cycle C, denoted by C, is a cycle with V(C)=V(C) and A(C)={(v, w)|(w, v)∈A(C)}. If there exists an isomorphic a, such thatσ(C)= C,then we say this cycle is self-conversed orσ-self-conversed.In this paper, we study the k-tuple domination number and particular cycles of de Bruijn and Kautz undirected graphs and digraphs. The article is divided into four chapters.In Chapter 1, we introduce some useful basic concepts.In Chapter 2, we study the k-tuple domination number in de Bruijn and Kautz graphs (denoted as UB(d,n) and UK(d,n)). The main results are as follows:(1) For d≥2 and 2d-1≥k≥2, we have(2) For d≥2 and 2d≥k>1, we haveIn Chapter 3, Suppose that d is even,we study the particular cycles of de Bruijn digraphs(denoted as B(d,n)). The main results are as follows:(1) For an even n>2, B(d,n) does not contain Hamiltonσ-self-converse cycles.(2) For n≥2, B(d,n) contains at least d/2σ-self-converse cycles of length 2n.(3) Suppose that n is odd. B(d, n) has aσ-self-converse cycle of length at least 4 if and only if there exists a path P= v1v2…in B(d,n) without crossing arcs andσ-fix vertices,such that(v1,σ(v1))and(vk,σ(vk))are crossing arcs,where k≤(dn)/2.(4)Suppose that n is even.B(d,n)has aσ-self-converse cycle of length at least 4 if and only if there exists a path P=v1v2…vk in B(d,n)without crossing arcs and with theσ-fix vertices v1,vk,where k≤((dn)/2+1).(5)Let n be odd.Then B(d,n)contains at least d/2σ-self-converse cycles of length 2n.(6)B(d,n)contains at least d/2σ-self-converse cycles of length 4.(7)If C is aσ-self-converse cycle of B(d,n),then L(C)is aσ-self-converse cycle of B(d,n+1).In Chapter 4,Suppose that d is odd,we study the particular cycles of Kautz di-graphs(denoted as K(d,n)).The main results are as follows:(1)For an even n≥2 and d≥3,K(d,n)does not contain Hamiltonσ-self-converse cycles.(2)Suppose that n is odd,K(d,n)has aσ-self-converse cycle of length at least 4 if and only if there exists a path P=v1v2…vk in B(d,n)without crossing arcs andσ-fix vertices,such that(v1,σ(v1))and(vk,σ(vk))are crossing arcs,where k≤((dn+d(n-1))/2.(3)Suppose that n is even.K(d,n)has aσ-self-converse cycle of length at least 4 if and only if there exists a path P=v1v2…vk in.B(d,n)without crossing arcs and with theσ-fix vertices v1,vk,where k≤((dn+d(n-1))/2+1.(4)If C is aσ-self-converse cycle of K(d,n),then L(C)is aσ-self-converse cycle of K(d,n+1).