Graphs are used to model many real life situations, and in such circumstances graph theory serves as a foundational structure to help explain the world in which we live. One very interesting application of graph theory is in the theory of the location of facilities in networks. The theory of location of facilities in networks combines tools from graph theory, basic analysis, optimization, and complexity theory. In this series of lectures we use the motivation from the theory of the location of facilities on networks to concentrate on some of the underlying graph theory. The goal of this series of talks is to convey the idea that this subject is a very accessible branch of applicable combinatorics, rich in problems, and offering an occasional surprise. Parts of the subject can be incorporated into the undergraduate classroom, both to illustrate a modern application of graph theory and to illustrate how applied problems can give rise to new questions in pure mathematics. The content is very suitable for stimulating departmental seminars and/or undergraduate lectures.

The major focus of the theory of location of facilities on networks is to determine where to locate facilities of some sort in a network of sites that include both potential facility sites and facility user sites. Facilities might be emergency installations, supply depots, switching stations, pumping stations, power facilities, transfer stations, communication devices, obnoxious facilities, or the like. Location(s) are required that "best" serve the users, where "best" is measured by criteria given in each particular example, some of which are required to be optimized over the network. Optimality depends on criteria usually involving some ideas of distance and costs, and varies according to the application. Weighted graphs, often referred to as networks, provide a context for studying these types of problems. Vertices and edges are assigned weights representing certain parameters (often some sort of costs) according to the application. Usually, special sets of points in the network are sought that are either "central" or "peripheral." Results in the literature range from the descriptions of optimal locations, to algorithms for locating optimal locations, to the computational difficulty in actually determining these optimal locations. Considerable study has been focused on weighted trees. These issues have motivated graph theorists to probe many different notions of central sets of vertices and notions of the "outer fringes" in ordinary (unweighted) graphs, particularly trees. In such models, users and facility locations are thought to be restricted to vertices. However, the graph theoretical origins of centrality precede the advent of modern location theory as C. Jordan introduced the concepts of the center of a tree and the branch weight centroid of a tree in 1869.

One major question that we will focus on during these lectures is: Where is the middle of a tree? We will see that there can be many different descriptions of the middle of a tree, some of which describe the same set. However, many descriptions lead to different central sets. We will also consider multiple centers, central sub-structures, anti-centrality, axiomatics, and some work on user preferences in determining locations. In addition, we will consider extensions of these ideas to graphs in general, and in some cases treat the network analogs.

Prerequisites: Participants should have good theorem proving skills, curiosity, enthusiasm for a new subject, and an acquaintance with graphs at least at the level of a discrete mathematics course.

References:

[1] N. Graham, R. C. Entringer, and L. A. Szekely, New tricks for old trees: Maps and the pigeonhole principle, Amer. Math. Monthly, 101 (1994), 664-667.

[2] S. L. Hakimi, Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12 (1964), 450-459.

[3] S. L. Hakimi, Optimal distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research, 12 (1964), 462-475.

[4] J. Halpern, The location of a center-median convex combination on an undirected tree, J. of Regional Science, 16 (1976), 237-245.

[5] G. Y. Handler, Minimax network location: theory and algorithms, Tech. Rept. No. 107. OR Center and FTL-R74-4, Flight Transportation Laboratory, Massachussetts Institute of Technology, Cambridge, 1974.

[6] F. Harary and P. Ostrand, The cutting center theorem for trees, Discrete Math., 1 (1971), 7-18.

[7] C. Jordan, Sur les assemblages des lignes, J. Reine Angew. Math., 70 (1869), 185-190.

[8] E. Minieka, The deliveryman problem on a tree network, Annals of Operations Research, 18 (1989), 261-266.

[9] S. Mitchell, Another characterization of the centroid of a tree, Discrete Math., 24 (1978), 277-280.

[10] O. Ore, Theory of Graphs, American Mathematical Society, Colloquium Publications, XXXVIII, Providence, R.I. (1962).

[11] K. B. Reid, Centroids to centers in trees, Networks, 21 (1991), 11-17.

[12] K. B. Reid, k-ball l-path branch-weight centroids of trees, Applied Discrete Mathematics, 80 (1997), 243-250.

[13] K. B. Reid, Balance vertices in trees, Networks, 34 (1999), 264-271.

[14] K. B. Reid, The latency center of a tree, Preprint (2001).

[15] K. B. Reid and Eli DePalma, Balance in trees, Preprint (2001).

[16] P. J. Slater, Maximin facility location, J. Research of the National Bureau of Standards B, 79B (1975), 107-115.

[17] P. J. Slater, Centers to centroids in graphs, J. Graph Theory, 2 (1978), 209-222.

[18] P. J. Slater, The k-nucleus of a graph, Networks, 11 (1981), 233-242.

[19] P. J. Slater, Accretion centers: a generalization of branch weight centroids, Discrete Appl. Math., 3 (1981), 187-192.

[20] P. J. Slater, On locating a facility to service areas within a network, Oper. Res., 29 (1981), 523-531.

[21] P. J. Slater, A survey of sequences of central subgraphs, Networks, 34 (1999), 244-249.

[22] C. Smart and P. J. Slater, Center, median, and centroid subgraphs, Networks, 34 (1999), 303-311.

[23] B. Zelinka, Medians and peripherians of trees, Arch. Math. (Brno), 4 (1968), 87-95.

[1] Mark S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons (1995).

[2] Z. Drezner (Editor), Facility Location, A Survey of Applications and Methods, Springer, New York (1995).

[3] H. W. Hamacher and Z. Drezner, Location Analysis, Theory and Applications, Springer, New York (2001).

[4] G. Y. Handler and P. B. Mirchandani, Location on Networks, The MIT Press, Cambridge, Massachusetts (1979).

[5] P. B. Mirchandani and R. L. Francis (editors), Discrete Location Theory, John Wiley & Sons, New York (1990).