A set S of nodes in a graph G = (V,E) is independent if no two nodes in S are adjacent. We present two types of self-stabilizing algorithms for finding disjoint independent sets R and B. In one type, R is maximal independent in G and B is maximal independent in the induced subgraph G[V−R]. In the second type, R is maximal independent in G[V−B] and B is maximal independent in G[V−R]. Both the central and distributed schedulers are considered.

Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating (broadcasting to) all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that ΣvεVf(v) is minimized, and such that every vertex u with f(u) = 0 is within distance f(v) of some vertex v with f(v)> 0. The problem is solvable in polynomial time on a general graph (Heggernes and Lokshtanov, Disc Math (2006), 3267–3280) and Blair et al. (Congr. Num. (2004), 55–77.) gave an O(n2) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on “nonlocal” information from vertices far away from v, whereas almost all other linear‐time algorithms for trees only make use of local information. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

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.

The problem of monitoring an electric 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 minimum cardinality of a power dominating set of a graph G is the power domination number $\gamma_P(G)$. We show that the power dominating set (PDS) problem is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give a linear algorithm to solve the PDS for trees. In addition, we investigate theoretical properties of $\gamma_P(T)$ in trees T.

Let S be a set of vertices in a graph $G = ( V,E )$. The authors state that a vertex u in S has a private neighbor (relative to S) if either u is not adjacent to any vertex in S or u is adjacent to a vertex w that is not adjacent to any other vertex in S. Based on the notion of private neighbors, a set of eight graph theoretic parameters can be defined whose inequality relationships can be described by a three-dimensional cube. Most of these parameters have already been studied independently. This paper unifies this study and helps to form a cohesive theory of private neighbors in graphs. Theoretical and algorithmic properties of this private neighbor cube are investigated, and many open questions are raised.

Abstract Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting one individual has an item of information which needs to be communicated to everyone else. We review the results that have been obtained on these and related problems.

In large organizations there is frequently a need to pass information from one place, e.g., the president’s office or company headquarters, to all other divisions, departments or employees. This is often done along organizational reporting lines. Insofar as most organizations are structured in a hierarchical or treelike fashion, this can be described as a process of information dissemination in trees. In this paper we present an algorithm which determines the amount of time required to pass, or to broadcast, a unit of information from an arbitrary vertex to every other vertex in a tree. As a byproduct of this algorithm we determine the broadcast center of a tree, i.e., the set of all vertices from which broadcasting can be accomplished in the least amount of time. It is shown that the subtree induced by the broadcast center of a tree is always a star with two or more vertices. We also show that the problem of determining the minimum amount of time required to broadcast from an arbitrary vertex in an arbitrarygraph is NP-complete.

Abstract A set D of vertices of a finite, undirected graph G = ( V, E ) is a total dominating set if every vertex of V is adjacent to some vertex of D . In this paper we initiate the study of total dominating sets in graphs and, in particular, obtain results concerning the total domination number of G (the smallest number of vertices in a total dominating set) and the total domatic number of G (the largest order of a partition of G into total dominating sets).

Abstract This paper presents a quick review of results and applications concerning dominating sets in graphs. The domatic number of a graph is defined and studied. It is seen that the theory of domination resembles the well known theory of colorings of graphs.

Abstract The Optional Hamiltonian Completion Problem is defined as follows: let the points V of a graph G be partitioned into a set V0 of optional points and a set V1 of non‐optional points; determine the minimum number of new lines which when added to G result in a graph which has a cycle containing every point of V1. This cycle may or may not contain optional points of V0. In this paper we present algorithms for solving this problem for trees, unicyclic graphs and cacti.

We develop linear-time algorithms to find maximum weighted and unweighted degree-constrained subgraphs (b-matchings) of a tree. We use a generalization of an algorithm for finding a maximum 2-matching in a tree.

article Free Access Share on Advances on the Hamiltonian Completion Problem Authors: S. E. Goodman Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , S. T. Hedetniemi Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , P. J. Slater National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, Iowa National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 3July 1975 pp 352–360https://doi.org/10.1145/321892.321897Published:01 July 1975Publication History 18citation522DownloadsMetricsTotal Citations18Total Downloads522Last 12 Months18Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A Hamiltonian walk in a graph G is a closed walk of minimum length which contains every point of G. An Eulerian walk in a graph G is a closed walk of minimum length which contains every line of G. In this paper we establish several relationships between Hamiltonian and Eulerian walks. We also derive a number of bounds on the length of a Hamiltonian walk.

The general problem of finding the shortest edge covering walks in an arbitrary undirected graph is investigated. An exact combinatoric expression is obtained for the length of such a walk, and the graph theoretic properties of these walks are studied. Explicit solutions are exhibited for some important classes of graphs.

article Free Access Share on 𝒮-Semigroups of Automata Authors: A. C. Fleck Department of Computer Science, The University of Iowa, Iowa City, Iowa Department of Computer Science, The University of Iowa, Iowa City, IowaView Profile , S. T. Hedetniemi Department of Computer Science, The University of Iowa, Iowa City, Iowa Department of Computer Science, The University of Iowa, Iowa City, IowaView Profile , R. H. Oehmke Department of Mathematics, The University of Iowa, Iowa City, Iowa Department of Mathematics, The University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 1Jan. 1972 pp 3–10https://doi.org/10.1145/321679.321681Published:01 January 1972Publication History 6citation314DownloadsMetricsTotal Citations6Total Downloads314Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A stationary maximin automaton is a system A = 〈S, U, f, h, F〉, where S and U are finite nonempty sets of states and inputs, respectively; F⊆S is a set of final states; f:S × U × S →[0, 1] can be imagined to be a transition relation which associates with every state s E S and input u E U a measure, 0≤ f(s,u,s') ≤ 1 that the next state is s', there being no constraint, for example, that the sum of these measures equals 1 for a given s and u. Similarly, the function h: S → [0, 1] defines something like an initial distribution, again with no constraints on the sum of all of the h(s)'s. What serves to distinguish maximin automata from other better known classes of automata is the manner in which the function f is extended to sequences of inputs x ∈ U*; this is defined as follows: