Study Of Neighbor Connectivity Of (Di-) Graphs

In modeling the spy network, Gunther and Hartnell proposed modelling it as a graphin which the vertices represent members of the resistance and the edges represent links ofcommunication. Unlike the conventional situation where the vertices of a graph representcomponents of a communication network that fail as individual elements, in the spynetwork scenario if a member is arrested, all of his or her neighbors are betrayed and soare rendered inefective. Hence in the graph model, whenever a vertex is "subverted", theentire closed neighborhood of the vertex is deleted from the graph. Hence they proposedthe concept of neighbor connectivity. This concept was generalized to its edge version byCozzens and Wu.This thesis is divided into three chapters. In Chapter1, we introduce the backgroundof our study. Then we state the main results in this thesis. In Chapter2, we study therelationship between the edge neighbor connectivity λNBof a graph G and the (vertex)neighbor connectivity κNBof its line graph L(G), and proved that λ_NB(G)≤κNB(L(G)).We also propose a new concept of restricted edge neighbor connectivity λ_NB^r(G), andprove that κNB(L(G))≤λ_NB^r(G). Then we study the problem of when the equalitieshold.In Chapter3, let G be a k-regular graph with girth at least4, connectivity k, andrestricted connectivity2k2. we proved that the edge neighbor connectivity of G×K2isk. As a consequence, the edge neighbor connectivity of n-dimensional hypercube is n1.Futhermore, we prove that the edge neighbor connectivity of K_n×K₂is n/2.In Chapter4, we give an algebraic characterization of the generating sets of Cayleydigraphs with neighbor connectivity equal to one for a class of Cayley digraphs thatincludes the Cayley digraphs of all abelian groups.