A Conjecture on the Maximum Value of the Principal Eigenvalue of a Planar Graph
Barry N. Boots, Gordon Royle · Geographical Analysis · 1991
It is now commonplace to see geographic networks represented as graphs.In particular, a network G, consisting of a finite set of vertices { u , , u 2 , . . ., u p ) together with links joining some of the pairs of vertices may be considered as a graph and encoded as a binary adjacency matrix A(G), in which u i j = 1 if there is a link between ui and uj and 0 otherwise.The majority of geographical applications involve planar graphs.In such instances more traditional indices of graph structure, including vertex-wnnectivity (see Bondy and Murty [1975] for graph theoretic terminology), sometimes fail to differentiate between graphs with very different topological properties (see James et al. [1970] and Cliff, Haggett, and Ord [1979] for examples).In particular, a planar graph can be at most five-connected regardless of its size.This experience led to the pioneering work of a u l d (1967) and Tinkler (1972), who suggested using properties of A(G) as measures of network structure.Using this approach several researchers have argued that the principal eigenvalue A, , , of A(G) can be used as a summary measure of overall network connectivity with larger values of A,,, being associated with more fully integratecl networks (Cliff and Ord 1977; ClifT, Haggett, and Ord 1979; Griffith and Jones 1980; Griffith, 1981, 1984; Amrhein, Guevara, and Griffith 1983; Boots 1984).The details of this procedure are given in Boots (1982, pp. 1063-64).However, there is at least one major difficulty associated with this approach.This is that we know that the value of A,,, depends in part on the size of the graph (that is, the number of vertices p ) .In general A,,, increases with p, although the exact form of the relationship has not been identified.Thus if we wish to use A, , , to compare the relative connectivity of networks of different sizes, we need some way of scaling A,,, to remove the size effects.Various ways have been proposed.For example, Griffith and Jones (1980, pp.190-91) suggest dividing by ( p -1) since this is the value that A,,, would take if the network were fully connected (that is, every pair of vertices were linked).The graph corresponding to a fully connected network on p vertices is called the complete gruph and denoted A version of this paper was presented at the Annual Meetings, Association of American Geo raphers, Baltimore,