An isolating set of a graph is a set of vertices S such that, if S and its neighborhood is removed, only isolated vertices remain; and the isolation number is the minimum size of such a set. It is known that for every connected graph apart from K 2 and C 5 , the isolation number is at most one-third the order and indeed such a graph has three disjoint isolating sets. In this paper we consider isolating sets where S is required to be an independent set and call the minimum size thereof the independent isolation number. While for general graphs of order n the independent isolation number can be arbitrarily close to n / 2 , we show that in bipartite graphs the vertex set can be partitioned into three disjoint independent isolating sets, whence the independent isolation number is at most n / 3 ; while for 3-colorable graphs the maximum value of the independent isolation number is ( n + 1 ) / 3 . We also provide a bound for k -colorable graphs.

Abstract Several algorithms for optimal vertex subsets in trees are given by simple tables. In this article we investigate the properties of and operations on these tables. We use known techniques for combining tables to correct a table in the literature; give a necessary and sufficient condition for a table to correspond to some tree property; discuss the question of dividing one table by another; explain how to derive a table from a set of representatives; and apply this to finding the table for the parameter external redundance. All of this is facilitated by computer software. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Summary form only given. A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. and Antonoiu et al. for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. There is a strong connection between k-forward numberings and colorings of graphs. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata, as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.

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 = 2, 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). © 1999 John Wiley & Sons, Inc. Networks 34: 312–319, 1999

Abstract In this paper, a schema of graphical parameters is proposed. Based on the parameter integrity introduced by Barefoot, Entringer, and Swart, members Ψ(G) of this schema have the general form Ψ(G) = min {|S| + Ψ(G ‐ S) : S Ψ V (G)}, where Ψ(G) is another given graphical parameter. Examples include integrity, mean integrity, connectivity, and vertex cover number. General results and bounds for the schema are derived. Also, properties that characterize such parameters are considered. © 1994 by John Wiley & Sons, Inc.

It is proved that every strongly connected directed graph with n nodes and at least $\lfloor ( n + 1 )^2 /4 \rfloor $ edges must contain an even cycle. This is best possible, and the structure of extremal graphs is discussed.

Randomized algorithms for two sorting problems are presented. In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order of every pair of adjacent vertices. In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set. Lower bounds for the problems in the comparison model are described and it is shown that the algorithms are optimal within a constant factor.

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally.We show that any n points in general position possess a crossing family of size at least ~, and describe an O(n log n)-time algorithm for finding one.

We present randomized algorithms for two sorting problems.In the local sorting problem, a graph is given in which each vertex is assigned an element of a total order, and the task is to determine the relative order in every pair of adjacent vertices.In the set-maxima problem, a collection of sets whose elements are drawn from a total order is given, and the task is to determine the maximum element in each set.We describe lower bounds for the problems in the comparison model, and show that the algorithms are optimal within a constant factor.