Week 2 Topic: Distance and Centrality Concepts in Graphs
July 17 - 21, 2000


Adam Buchsbaum, AT&T Labs - Research

Massive Graph Algorithmics
Joint work with J. Abello and J. Westbrook

Communications networks and the traffic they carry can be modeled as graphs. For example, each customer is a vertex, and a transaction (e.g., a telephone call) between two customers is an edge. The resulting graphs are quite large: the AT&T voice network carries two to three hundred million calls on a typical business day; over time, the number of customers seen is also two to three hundred million. The induced graphs contain a wealth of information, but standard graph algorithms assume that graphs fit in main memory and do not scale to process such massive graphs efficiently.

I will review one standard model of algorithmic complexity and show how it breaks down for out-of-core data. I will then introduce a newer model that stresses data transfer over computation and demonstrate how it leads to some effective graph algorithms. Finally, I will show some of the data we have been able to analyze as a result.

Fred Buckley, Baruch College - CUNY

Mutually eccentric vertices in graphs
Joint work with W.Y. Lau

The distance between a pair of vertices u and v is the length of a shortest path joining u and v. The eccentricity e(v) of vertex v is the distance to a vertex farthest from v. The center of graph G is the set of vertices with minimum eccentricity, and the periphery is the set of vertices with maximum eccentricity. In a graph G, an eccentric vertex of v is a vertex farthest from v in G, that is, a vertex u for which d(u,v) = e(v). Given a set X of vertices in G, the vertices of X are mutually eccentric provided that for any pair of vertices u and v in X, u is an eccentric vertex of v and v is an eccentric vertex of u. We discuss problems concerning sets of mutually eccentric vertices in graphs with particular attention paid to mutually eccentric central vertices and mutually eccentric peripheral vertices.

Peter Dankelmann, University of Natal at Durban

Average Distance in Graphs

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. The average distance has been investigated by several authors and under different names, such as mean distance, total distance, transmission, routing cost, and Wiener index. In this talk we present a survey of results on the average distance of graphs. We give several bounds relating it to other graph invariants, in particular to order, size, minimum degree, independence number, domination number, and matching number.

We also discuss algorithmic aspects of the average distance. We present results on the computation of the average distance and on the problem of finding a minimum average distance spanning tree of a given graph.

We conclude the talk with a brief investigation of generalisations of the average distance.

Jean Dunbar, Converse College

The Path Partition Conjecture and its Cousins
Joint work with M. Frick

The detour order T(G) of a graph G = (V,E) is the order of a longest path of G.

A partition {A,B} of V is called an (a,b)-partition if T(G[A]) <= a and T(G[B]) <= b. The Path Partition Conjecture is the following:

For any graph G, with detour order T(G) = a + b, there exists an (a,b)-partition of the vertices of G.

A subset K of V is called a Pn-kernel of G if it is Pn-free and every vertex of V - K is adjacent to an endvertex of a Pn-1.

We examine two (possibly stronger) conjectures:

Conjecture 2: Every graph has a Pn-kernel for every positive integer n.

Conjecture 3: If M is a maximum Pn+1-free subgraph of G, with n < T(G), then T(G - M) <= T(G) - n.

We investigate the relationships among these conjectures and find classes of graphs for which the conjectures hold.

David Erwin, Western Michigan University

Radio labelings of graphs
Joint work with G. Chartrand, F. Harary and P. Zhang

Informally, a radio labeling is a simplified, abstract model of FCC regulations governing the assignment of frequencies to commercial FM stations. Formally, a radio labeling of a connected graph G is an assignment of distinct positive integers to the vertices of G, with x labeled c(x), such that d(u,v) + |c(u)-c(v)| >= 1 + diam G for every two distinct vertices u,v of G. The radio number rn(c) of a radio labeling c of G is the maximum label assigned to a vertex of G. The radio number rn(G) of G is min{rn(c)} over all radio labelings c of G. We shall discuss the radio numbers of several classes of graphs and also describe some more general bounds. We shall probably also mention related work on the antipodal chromatic number and radio colorings.

David Fisher & Anne Spalding *
University of Colorado at Denver
* Mesa State College, Grand Junction, Colorado

Knight Covers of Rectangular Boards

A set of Knights covers a board if they attack every Knightless square. What is the minimum size of a Knight cover for a kxn board? By finding periodicity in an algorithm of Hare and Hedetniemi, we answer this question and give minimum covers for all n when k<=10. We also count minimum covers for k<=9 and n<=49.

Michael Gargano, Pace University

John Gimbel, University of Alaska at Fairbanks

Alan Goldman, Johns Hopkins University

Optimal location of a mesometric facility
Joint work with M. Deeney

Mesometric facilities are a "third generation" class, neither purely attractive nor purely obnoxious. Motivating scenarios, including some in non- "physical" spaces, are identified. The corresponding optimization problems are nasty (non-convex, non-concave): applicability of "dc programming" algorithms is explored. A complete analytical solution for a natural class of 1-dimensional models is sketched, including verification of a "migration hypothesis" conjectured to hold more generally. For 1-center problems on a network with n vertices and m edges, the domain is shown reducible, with effort low-order polynomial in (n,m), to a certain "finite dominating set" of low-order polynomial size, a result in the spirit of that of Church and Garfinkel (1978) for obnoxious facilities. Finally, various further research issues are identified, in particular difficulties in the modelling of multi-facility situations.

Weizhen Gu, Southwest Texas State University

A central appendage number of a uniform central graph

A graph is called a uniform central graph if the eccentric sets of all central vertices are the same. A central appendage number of a graph G, denoted by Aucg(G), is the minimal number of vertices to be added to G such that the resulting graph H is a uniform central graph with C(H)=G (C(H) is the center of H). In this paper we prove that for any graph G, 2<= Aucg(G)<= 6. Also we characterize all graphs G for which Aucg(G) = 2, 4, or 6.

Sudipto Guha, Stanford University

Improved Approximation Algorithms for Fault Tolerant Facility Location

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. Every demand point j is served by rj facilities instead of just one. The facilities other than the closest one are ``backup'' facilities for that demand, and will be used only if the closer facility (or the link to it) fails. Hence, for any demand, we assign non-increasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its rj closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve this result to 3.16 using randomization and to 2.47 using greedy local-search type techniques.

Teresa Haynes, East Tennessee State University

Power domination in graphs applied to electrical power networks
Joint work with S.M. Hedetniemi, S.T. Hedetniemi and M.A. Henning

The problem of monitoring an electrical power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number of a graph G is the minimum cardinality of a power dominating set of G. We show that the power dominating set problem (PDS) is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give an linear algorithm to solve PDS for trees. We also investigate theoretical properties of the power domination number in graphs.

Stephen Hedetniemi, Clemson University

Locating Roman Legions Optimally
Joint work with E.J. Cockayne, P.A. Dreyer, Jr. and S.M. Hedetniemi

A Roman dominating function (RDF) on a network G = (V,E) is an assignment f: V -> {0,1,2} of Roman Legions to some of the locations in the network, such that every location u having no Legion assigned to it (f(u) = 0) is adjacent to at least one location v having two Legions assigned to it (f(v) = 2). If a location u has no Legion assigned to it, then it must be possible to send a Legion to defend it from a neighboring location v, subject to Emperor Constantine's decree that no Legion can leave a location v to defend another location unless a second Legion is also stationed at v. The cost of a Roman dominating function is the total number of Legions assigned to locations in the graph. We study the graph theoretic and computational aspects of this historical facility location problem.

Michael Henning, University of Natal at Pietermaritzburg

Generalized eccentricity, radius and diameter in graphs
Joint work with P. Dankelmann, W. Goddard and H.C. Swart.

For a vertex v and a (k-1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum distance over all P, and the k-eccentricity of the set P as the maximum distance over all v. If k=3D2 one is back with the normal eccentricity. We study here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity).

Genie Jackson, East Tennessee State University

Domination-good and domination-bad vertices in trees

For a graph G = (V,E), a set S of V(G) is a dominating set if every vertex in V-S is adjacent to some vertex in S. A vertex v in V(G) is called good if it is an element of a dominating set of minimum cardinality in G; otherwise, the vertex is called bad. Let g(G) and b(G) denote the number of good and bad vertices, respectively, of G. Then a graph G is classified according to its good and bad vertices as follows: G is domination-excellent if g(G) = |V(G)|, is domination-commendable if g(G) > b(G) > 0, is domination-fair if g(G) = b(G), and is domination-poor if g(G) < b(G). We investigate trees in each of these categories.

Garry Johns, Saginaw Valley State University

Using degrees to characterize distance-related subgraphs
Joint work with P. Brown

In a connected graph G, the distance of a vertex is defined as the sum of the distances from v to all other vertices of G. When each vertex is assigned this value, the median of G is defined as the subgraph induced by those vertices with minimum distance and the margin of G is the subgraph induced by the vertices of maximum distance. It is known that every graph can be the median and margin of other graphs. Also, in a graph of diameter 2, there is a useful relation between the degree of a vertex and its distance. In this paper, we extend these ideas in three ways. First, we define three other subgraphs of G by using the vertices with the intermediate values of distance: the lower middle, the perfect middle, and the upper middle. Second, we characterize those graphs that can be one of the various middle subgraphs, and third, we investigate for a given graph G and a specified subgraph (median, perfect middle, etc.), the number of vertices that must be added to V(G) to form a graph H so that G forms that subgraph of H.

Sulamita Klein, University of Paris

Liping Ma,

Teachers' Understanding of Math in China and the United States

Buck McMorris, Illinois Institute of Technology

Characterizations of some location functions on graphs

Let X be a finite metric space and S a subset of X. For x in X, let D(x,S) be a measure of remoteness of x to S, and let L be the function where L(S) is the set of points x in X for which D(x,S) is minimum. L is called the median function on X when D(x,S) is the sum of distances of x to points in S, the mean function on X when D(x,S) is the sum of distances squared, and the center function on X when D(x,S) is the max of the distances of x to points in S. This talk will review some recent results characterizing the median, center and mean functions when X is a tree equiped with the usual graph metric.

Martyn Mulder, Erasmus University of Rotterdam

Location strategies on graphs

A profile on a connected graph G is a sequence of vertices of G. A median of a profile is a vertex x of G minimizing the sum of the distances between x and the elements of the profile. The median function M on G returns for each profile the set of the medians of the profile. We discuss simple strategies to construct the median function on several classes of graphs. We explore these ideas in various ways to find strategies for other Location Functions, and present some open problems.

Christine Nickel, Johns Hopkins University

Ortrud Oellermann, University of Winnipeg

Steiner distances in graphs and centrality measures and structures

The Steiner distance of a set S of vertices in a connected graph G is the smallest number of edges in a connected subgraph of G that contains S. For an integer n > 2, the n-eccentricity of a vertex v of G, is the maximum Steiner distance taken over all n-sets of vertices of G that contain v. The smallest n-eccentricity among all vertices of G is called the n-radius of G and the largest n-eccentricity among all vertices of G is called the n- diameter of G. Relationships between the n-diameter and the n-radius of a graph are presented. The subgraph induced by the vertices of minimum n-eccentricity is called the n-center of the graph. The n-distance of a vertex v in a graph is called the sum of the Steiner distances of all n-sets of vertices that contain v. The subgraph induced by the vertices of minimum n-distance is called the n-median of the graph. Structural characterizations of n-centers and n-medians are presented and it is shown that these subgraphs can be arbitrarily far apart. Centrality structures that extend those of the n-center and n-median are defined and it is shown that every vertex on a shortest path from the n-center to the n-median of a tree belongs to one of these centrality structures. Some open problems will also be discussed.

James B. Phillips, University of Alabama - Huntsville

Colored Distance in Grid Graphs

For a graph facility location problem, each vertex is considered to be the location of a department or facility. One seeks to optimally locate these facilities in order to minimize some function of the distances between departments. For example, consider a plant or factory that has a rectangular planar area where L is the length and W is the width. Suppose that there are t-departments ans department i requires a total area of n_i and the sum of the n_i's is equal to L*W, the total area. Members of the same department are not required to talk to each other but must talk with everyone else in each of the other departments. Here, we seek to minimize the total distance between members of different departments. We assume that each member is a 1x1 grid. Thus each department i has a total of n_i 1x1 grids, but these grids are not required to be adjacent. This problem is a particular instance of the colored distance problem, in which a general graph is colored with t-colors and the colored distance is the sum of the distances between vertices of different colors. Meiers and Slater studied the two color grid graph problem and we discuss preliminary results on an extension of those results to the general case for t-colors where t>=2, with an emphasis on the equitable case where all colors occupy an equal number of vertices in the grid.

Kenneth Proffitt, East Tennessee State University

Justo Puerto, Universidad de Sevilla

Ordered median problems on networks
Joint work with S. Nickel and J. Kalsics.

In this paper we address a type of facility location problems on networks which includes as special cases most of the classical criteria in the literature. Structural results as well as finite dominating sets for the optimal locations are developed. We investigate the existence of a finite set of candidates to be optimal solutions for a wide range of location problems on networks: the so called p-facility ordered median problem. Finite dominating sets (FDS) are known for particular instances of this problem: p-median, p-center, p-centdian. Our aim is to study the structure of the set of candidate points to be optimal solutions for all these problems showing the similarities existing between them. The frontiers for finding easy finite dominating sets are shown. For a special subclass of ordered median problems a polynomial algorithm on trees is proposed. This algorithm is a generalization of existing ones for the p-median and the p-centdian problems.

Louis V. Quintas, Pace University

Distance problems in graphs whose vertices are graphs
Joint work with K.T. Balinska, G.R. Brightwell and J. Szymanski.

Let G = (V,E) be a graph such that its vertex set V is a set of graphs and {X,Y} is in its edge set E if and only if the graph Y can be obtained from the graph X by the insertion or deletion of a single edge of X.

Graphs G of this type, with appropriate embellishments, play a role in a variety of contexts. For example, G can be the transition digraph for a random process, the vertices of G can be interpreted as molecular graphs, or G can be studied strictly with respect to its graph theoretical properties.

Define the distance d(X,Y) between two vertices X and Y of G as the least number of insertions and/or deletions of edges needed to obtain Y from X, that is, d(X,Y) is just the graph theoretical distance between X and Y. Our focus will be on the distance properties of G. Namely, for a given vertex set we are interested in the diameter, radius, center, and periphery of G. Vertex sets consisting of (i) all graphs having order n, (ii) all graphs having order n and maximum vertex degree f, and (iii) all forests having order n and maximum vertex degree f, will be discussed.

K. Brooks Reid, California State University, San Marcos

Where is the middle of a tree?

There are two very standard "central sets" of vertices in a tree, the center and the median (which is the same as the branch weight centroid). Many other "central sets" have been proposed as being the middle of a tree. In this talk we discuss some "central sets" that we have proposed for a tree T. First we discuss the set of balance vertices in T, vertices that might be considered as discrete versions of the center of gravity. There are trees in which the center, the median, and the set of balance vertices are singletons, each two of which are far apart. Second, we discuss a one-parameter family of "central sets," the k-ball branch weight centroid. This family contains both the center (when k is the radius of T) and the median (when k = 0). And, third, we discuss a two-parameter family of "central sets," the k-ball p-path branch weight centroid. This family actually contains the previous family when p = k+1. We will compare these families to two of P. Slater's families of "central sets," the k-centra and the k-nuclei (which is the same family as Z. Winn's k-branch weight centroids).

Zhizhang Shen Plymouth State College

The calculation of average distance in mesh structures

Mesh structure is a natural choice among several distributed memory architectures, when studying problems in such areas as image processing, computer vision, and computer geometry, with a parallel architecture. In this paper, we analyze a scalable measurement of average distance between two specific processors in mesh structures. Such a notion is useful in providing a more global network measurement in characterizing its behavior when carrying out multicasting, as well as unicasting, communication. In particular, we provide a closed-form expression for the average distance between two processors in the case of traditional mesh. For a more sophisticated case, where a tradition mesh is augmented with additional diagonal links, we provide a pretty elegant and telling expression for the same quantity. However, we will show that this quantity, i.e., the average distance between two processors, for this augmented structure cannot be expressed in a closed-form expression, with respect to a fairly general class of "standard operations", namely, hypergeometric terms.

Besides suggesting another global measurement of the communication behavior for general computer networks, and deriving concrete results for "popular" mesh structures, this paper provides both positive and negative results regarding the derivation of closed-form expressions for combinatorial quantities, thus is also theoretically interesting. We believe that some of the general techniques used in this paper should be applicable else where when closed-form expression needs to be derived, or its existence is in question.

Peter Slater, University of Alabama - Huntsville

Distance, Centrality and Facility Location

Graphs and networks model systems, such as communications and transportation systems, in which costs associated with transmission or carrying times are generally nondecreasing functions of the distance between the points involved.In this context, one might be interested in designing an overall "compact" network (subject to certain constraints) or in selecting points in an existing network at which to place "centrally" located facilities. However, different measures of centrality can identify distinct, and, in fact, arbitrarily far apart, locations as optimal.

This introductory lecture will contain a general discussion of distance, centrality and location questions. Included will be a set of questions, from elementary (?) to the as yet unsolved to get the week started.

Henda Swart, University of Natal

On the average Steiner distance of a graph
Joint work with P.A. Dankelmann, O.R. Oellermann

For n>1, the average Steiner n-distance of a graph G is the average Steiner distance over all sets of n vertices in G. We establish properties of and bounds on the parameter for connected graphs, with particular reference to trees, 2-connected graphs and k- chromatic graphs.

Arie Tamir, Tel Aviv University

Facility Location Problems on Tree Graphs with Different Speeds for Customers and Servers:
A Study on Covering Problems Defined by Families of Subtrees

In the classical p-center problem on a network there are customers located at the nodes of the network, and the objective is to locate p servers (centers) in order to minimize the maximum travel distance between the customers and their respective nearest servers. If customers travel to the servers, possibly at different speeds, an appropriate objective is to minimize the maximum travel time. Assuming constant speeds, the latter case reduces to the classical weighted p-center problem, where distances are weighted by the customer speeds. A symmetric model, where servers travel to the customers might be appropriate for other practical situations. We have been motivated by an application which unifies both models. Suppose that in an emergency situation a customer places a call for help. The customer has a vehicle that can start traveling immediately, in any direction at a given speed. There are p servers (emergency crews) on the network, and they may also have different speeds. The objective is to minimize the response time, i.e., find a server that will instantenously start moving towards the customer, minimizing the travel time elapses till the customer meets the server. The problem is to find the location of p servers, minimizing the maximum response time to the customers. We are unware of any previous studies of this problem, where both customers and servers may move simultaneously at different velocities. We discuss this generalized center location problem, and study some of its variations, depending on the nature of the set of points, where customers and servers are allowed to meet.

This generalized p-center problem is clearly NP-hard. Here we focus on tree networks and study the properties of the mathematical model. In particular, we present polynomial algorithms.

Steven Winters, University of Wisconsin at Oshkosh

Using Graphs for Facility Location Problems

Graph theory is an exciting and rapidly growing area of mathematics rich in theoretical results as well as applications to real-world problems. Many situations and structures give rise to graphs. For example, a street system for a city can be modelled by a graph where each intersection corresponds to a vertex and each street to an edge. Then an emergency facility should be placed at a location that minimizes the maximum response time in the city. The best location of a service facility minimizes the total distance for everyone in the city to travel to this location. But in reality, it is common to have a road blocked due to road construction or an accident. This talk will investigate the best location for facilities when a road is blocked at random.

Updated July 13, 2000