Generalized Distance in Graphs
Garry L. Johns · ScholarWorks - WMU (Western Michigan University) · 1988
INARIES 1.1 Introduction Historically, graphs have been used as models for studying the structure and relationships in many real-world situations.One relationship that has received considerable attention is the distance between vertices of a graph.For a connected graph G and a pair u,v of vertices of G, we define the distance da(u, v) (or simply d(u, v)) as the length of a shortest u -v path in G.With the aid of an algorithm developed by Dijkstra [7], computing distances is straightforward.Many applications require altering the definition of distance; however, one concept has always been of interest, namely, the idea of "centrality".Intuitively, in a graph G, the "central" vertices are those vertices of G whose distance to all other vertices of G is "small."This idea of "centrality" has led to the study of graphical structures such as centers, centroids, ^-centra and medians (see [6]).Recently, applications have arisen where we consider the opposite ex treme.That is, we consider "boundary" vertices in a graph G whose distance to all other vertices of G is "large."Many of the results in this dissertation deal with these "boundary" vertices.1 R e p r o d u ce d with p erm issio n of th e cop yrigh t ow n er.Further reprodu ction prohibited w ithout p erm ission .The primary purpose of this dissertation is to study generalizations of distance in graphs.In Chapters II and V, we introduce, for a connected graph G, new definitions for the distance between vertices of G and the distance between subgraphs of G, respectively.In Chapters III and IV, we expand on known results; namely, the distance of a vertex and antipodal graphs.In Chapter II, we define, for a connected graph G, a subset 5 of V(G) and vertices u, v of G, the 5-distance ds(u,v) from u to v as the length of a shortest u -v walk in G that contains every vertex of 5. We also consider the 5-eccentricity es(v) of a vertex v, the 5-radius of a graph and the 5-diameter diams(G) of a graph G.We then define the 5-center of a graph and show, for every graph G and each nonnegative integer n y-1, that there exists a graph H and a subset 5 of V(H) with |5| = n such that the 5-center of H is isomorphic to G. Similarly, we define the 5-periphery of a graph and, for a graph G and a positive integer n, we show that there exists a graph H and a subset 5 of V(H) with |5| = n such that the 5-periphery of H is isomorphic to G.An unusual property of 5-distance is that, for a connected graph G and a subset 5 of V(G), there often exists a vertex v such that ds(v,v) = diams{G).Several sufficient conditions are given for a graph G that insure the occurrence of this property.Several results for 5-distance in trees are presented and the chapter is concluded by studying the n-eccentricity en(v) for a vertex v where en(v) = max es(v).R e p r o d u ce d with p erm issio n o f th e cop yrigh t ow n er.Further reprodu ction prohibited w ith ou t p erm ission .be a pairing from V(F) to V(H) such that d(F, H) = ^( F , i f ) and = ui for a maximum number n of vertices in {u i, u2, u*}.Without loss of generality, suppose that 7T 1(m1) ^ u\.Now, let 7Tx(mi) = v and u G V (F ) satisfy ir(u) = u\.Then d(u, v) 1 is the periphery of a connected graph H if and only if A(G) < p -2 or G = Kp.R e p r o d u ce d with p erm issio n of th e cop yrigh t ow n er.Further reproduction prohibited w ithout p erm ission .We will write F C G if the graph F is a subgraph of the graph G and F -< G if F is an induced subgraph of G.As a matter of convenience for the reader, the symbol • is used to designate the end of a proof.R e p r o d u ce d with p erm issio n o f th e cop yrigh t ow n er.Further reproduction prohibited w ithout p erm ission .