Abstract One of Frank Boesch's best known papers is ‘The strongest monotone degree condition for n‐connectedness of a graph’ (Boesch, J Combinatorial Theory Ser B 16 (1974), 162–165.). In this article, we give a simple sufficient degree condition for a graph to be k‐edge‐connected, and also give the strongest monotone condition for a graph to be 2‐edge‐connected. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We begin by examining the dynamic behavior of a facility location such as a 1-median or a 1-center on a network when the parameters of the network are known functions of time. The parameters of the network include the lengths of the edges and the demands at the nodes. In our formulation, time is considered a discrete variable and it is assumed that the facility can only serve customers while it is stationary and that the demands at time t are fully satisfied before time t + 1. In particular, if x(t) denotes the location of the facility for t = 1, 2, … , the cost would be the sum of the costs of satisfying the demands at the various times plus the cost of moving the facility along its route implied by x(t). We also examine certain path (route) selection problems in dynamic networks. Recent past literature is surveyed. Various extensions including the multifacility versions of the above problems are studied. © 1999 John Wiley & Sons, Inc. Networks 34: 250–257, 1999

It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in order to maximize the number of ordered vertex pairs (x, y) such that there is a directed path from x to y. After transforming this problem, we prove a key theorem about the transformed problem that allows us to obtain a quadratic algorithm for the original orientation problem. We also consider how to orient graphs to minimize the number of ordered vertex pairs joined by a directed path. After showing this problem is equivalent to the comparability graph completion problem, we show both problems are NP-hard, and even NP-hard to approximate to within a factor of 1 + ε, for some ε > 0.

We study the problem of locating replicas of a database on a network to minimize the communication cost. We first present extensions of the p-median theorem to prove that under two different measures of communication cost one can always optimally locate the replicas at the vertices (nodes) of the network. We briefly review the fact that the problem is NP-hard for general networks under either measure of communication cost, and we then provide efficient algorithms for solving the problem on tree networks for either of the two measures. © 1997 John Wiley & Sons, Inc. Networks 30:31–36, 1997

Each vertex of an undirected graph possesses a piece of information that must be sent to every other vertex. They communicate by sending bounded size packets of messages from one vertex to another. The authors describe parallel algorithms, which accomplish the desired tasks for six prominent architectures. The algorithms are optimal, or nearly so, in every case.

Abstract The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of the p‐Median theorem. © 1993 by John Wiley & Sons, Inc.

This paper considers the following problem: Given a positive integer t and graph H, construct a graph G from H by adding a minimum number $\Delta ( t,H )$ (respectively, $\Delta ' ( t,H )$) of edges and an appropriate number of vertices, such that after removing any t vertices (respectively, t edges) from G the remaining graph contains H as a subgraph. This problem was motivated by the design of fault-tolerant interconnection networks for multiprocessor systems. The authors estimate $\Delta ( t,H )$ and $\Delta ' ( t,H )$ for the cycle, path, complete binary tree, grid, torus, and hypercube on n vertices.

Consider a network in which each unit initially knows only its own identity and the identity of its immediate neighbors. Suppose each unit has a message intended for all other units. The authors give a distributed algorithm to accomplish this in point-to-point networks which is optimal in the number of transmissions it requires. They also show that this algorithm accomplishes this efficiently for broadcast (radio) networks, although the problem of finding a solution with the least number of transmissions, in broadcast networks, is shown to be NP-hard.>

Given a network N(V, E) and a set of points Xp = {x1, …, xp} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x1), …, T(xp). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting Xp so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract Consider a network consisting of units and links that connect pairs of units. Suppose each of the units possesses a unique message that is to be received by all other units. This is called gossiping. A related problem is that of census taking in which a particular unit has to receive every other unit's message. We study gossiping and census taking in a network in which the units communicate by transmitting packets of a fixed size, so that only a bounded number of messages can be sent in a single transmission. We also discuss the complexity of gossiping when the messages are of different sizes.

The vertex arboricity$a(G)$ of a graph G is the minimum number of subsets into which the vertices of G can be partitioned so that each subset induces an acyclic graph. A characterization of planar graphs G is given for which $a(G) = 2$, thereby answering a question of Grünbaum [Israel J. Math., 14 (1973), pp. 390–408]. The characterization is in terms of the dual graph $G^* $. As a corollary, a theorem of Stein that characterizes maximal planar graphs G with $a(G) = 2$ is obtained. This latter result implies that determining whether $a(G)\leqq 2$ is NP-complete for maximal planar graphs G.

Abstract A graph G is called hypohamiltonian if G is not hamiltonian but every vertex‐deleted subgraph G‐v is hamiltonian. The existence of a p‐vertex hypohamiltonian graph is open only for p = 14,17, and the existence of a p‐vertex, cubic hypohamiltonian graph is open only for p = 14,16,24,32. With the aid of a computer we have established that there is no hypohamiltonian graph of order 14, and no cubic hypohamiltonian graph of order 14 or 16. In addition, there is no hypohamiltonian graph of order 17 with girth ≥ 5. On the other hand, new p‐vertex, cubic hypohamiltonian graphs have been found for p = 18,22.