Figure Circle And Network Reliability Parameters

This thesis is the result of almost four years of research in the field of graph theory. Except the first introductory chapter the reader will find five chapters that contain two topics within this research field.The first part is composed of only chapter one. Chapter 1 is intended as an introduction to the background material together with the relevant terminology and notations, for the problems being studied in the following two parts.The second part is composed of two chapters, mainly dealing with the cycle properties of graphs. In Chapter 2, we study the pancyclic properties of block-intersection graphs of balanced incomplete block designs, often abbreviated as BIBD. Aside from an early result of Horak and Rosa pertaining to BIBD block intersection graphs, none of these initial results applied to designs having indexλ＞1. In this thesis we study the case when A≥1, and prove that the block-intersection graph G_D of BIBD(ν,κ,λ) is pancyclic (for the definition of block-intersection graph see section 1.1). In 1998, AinoUche[1] introduced the concept of quasi-claw-free graph. Since then a variety of known results on claw-free graphs, dealing with hamiltonicity and circumference, were extended to the large class of quasi-claw-free graphs. In Chapter 3, we extend the result on circumference of 2-connected claw-free graphs to the 2-connected quasi-claw-free graphs. We prove that the circumference of a 2-connected quasi-claw-free graph G(?)F on n vertices is at least min{3δ+2, n}, and G is hamiltonian if n≤4δ, where F is a class of nonhamiltonian graphs of connectivity 2 (for the definition of quasi-claw-free graph see section 1.2).The third part contains three chapters, in which we determine the vulnerability parameters of some classes of graphs. If we take a graph G as a modelling of a communication network, many graph parameters can be used to describe the vulnerability of communication networks. For two graphs having the same connectivity and having the same number of vertices after a disruption, the number of vertices of their largest components can be different. This implies, in a communication network, the size of the largest remaining group within which mutual communication can still occur will be different. At this point, the connectivity of a graph is not enough to measure the vulnerability of a network. It is important to determine the parameters such as, the scattering number, the toughness and the integrity of a graph when they are used to measure the vulnerability of networks (for the definitions of these vulnerability parameters of graphs see section 1.3).Since most of the problems of computing the vulnerability parameters of a generalgraph are NP'hard, it is an interesting problem to study the vulnerability parameters of specific classes of graphs.In third part we mainly dealing with the vulnerability parameters of some special classes of graphs. Th.ese parameters have a strong connection with cycles in graphs.In part three, we useα,β,σ,κandδto denote the independence number, covering number, domination number, connectivity and the minimum degree of a graph, respectively, and useε(G), andν(G) to denote the number of edges and the number of vertices of G, respectively (for the definitions of these parameters, see section 1.3)For two vertices u and v in a graph G, we use u～v to denote that u and v are adjacent in G.The Kroneckerproduct (also named direct product or×product) G₁×G₂ of two graphs G₁ and G₂ has vertex set V(G₁)×V(G₂), and E(G₁×G₂)={(u₁,v₁)(u₂, v₂): u₁u₂∈E(G₁)and v₁v₂∈E(G₂)}.In Chapter 4, we determine the scattering number s(G) of the product of two complete graphs and the product of a path (cycle) and a complete graph.(1.) Let m and n be integers not less than 3. Then(2.) Let m, n be integers with m≥2, n≥3. Then(3.) Let m and n be integers not less than 3. Then In Chapter 5, we deal with the middle graph M(G) of certain type of graphs G. For a graph G, the middle graph M(G) is the graph with vertex set V(G)∪E(G) in which the vertices x and y arejoined by an edge if one of the following conditions holds: (â…°) x, y(?)E(G), and x and y are adjacent in G, (â…±) one ofx and y is in V(G) and the other is in E(G), and they are incident in G.We obtain the following results on the vertex vulnerability parameters of the middle graphs.1. For any graph G(a)β(M(G))=ε(G);(b)α(M(G))=ν(G);(c)δ(G)+1≤I(M(G))≤ε(a)+1;(d) I(M(G))≥1+ε(G)/ν(G)+(1-1/ν(G))κ'(G)≥1+ε(G)/ν(G).2. Let P_n, C_n, W_1,n and K_n denote the path, cycle, wheel and complete graph, respectively. Then 3. If T is a tree with n vertices, then I(M(T))≤I(M(K_1,n-1))=n.In Chapter 6, we prove the following result on the vertex vulnerability parameters of the product of complete graphs.Let m, n be integers with n≥m≥2 and n≥3. Then(a)κ(K_m×K_n)=(m-1)(n-1).(b) t(K_m×K_n)=m-1.(c) I(K_m×K_n)=mn-n+1.(d) T(K_m×K_n)=m+1/2-1.