Search

Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G − R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm _ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.

A coalition in a graph G=(V,E) consists of two disjoint sets V1 and V2 of vertices, such that neither V1 nor V2 is a dominating set, but the union V1∪V2 is a dominating set of G. A coalition partition in a graph G of order n=|V| is a vertex partition π=V1,V2,...,Vk such that every set Vi either is a dominating set consisting of a single vertex of degree n-1, or is not a dominating set but forms a coalition with another set Vj. Associated with every coalition partition π of a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G,π), the vertices of which correspond one-to-one with the sets V1,V2,...,Vk of π and two vertices are adjacent in CG(G,π) if and only if their corresponding sets in π form a coalition. In this paper, we initiate the study of coalition graphs and we show that every graph is a coalition graph. [ABSTRACT FROM AUTHOR]

A path π = (v1, v2, . . . , vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds

A coalition in a graph G = (V,E) consists of two disjoint sets V1 and V2 of vertices, such that neither V1 nor V2 is a dominating set, but the union V1 ∪ V2 is a dominating set of G. A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1, V2, . . ., Vk} such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition π of a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G, π), the vertices of which correspond one-to-one with the sets V1, V2, . . ., Vk of π and two vertices are adjacent in CG(G, π) if and only if their corresponding sets in π form a coalition. The singleton partition π1 of the vertex set of G is a partition of order |V |, that is, each vertex of G is in a singleton set of the partition. A graph G is called a self-coalition graph if G is isomorphic to its coalition graph CG(G, π1), where π1 is the singleton partition of G. In this paper, we characterize self-coalition graphs. [ABSTRACT FROM AUTHOR]

A coalition in a graph G = (V;E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G. A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1; V2, . . ., Vkg of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition &#960, of a graph G is a graph called the coalition graph of G with respect to &#960, denoted CG(G, &#960,), the vertices of which correspond one-to-one with the sets V1, V2, . . ., Vk of &#960, and two vertices are adjacent in CG(G, &#960,) if and only if their corresponding sets in &#960, form a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs. [ABSTRACT FROM AUTHOR]

A setSof vertices is a total dominating set of a graphGif every vertex ofGis adjacent to some vertex inS. The minimum cardinality of a total dominating set is the total domination numberγt(G). A Roman dominating function on a graphGis a functionf:V(G) → {0, 1, 2} satisfying the condition that every vertexuwithf(u)=0 is adjacent to at least one vertexvofGfor whichf(v)=2. The minimum off(V(G))=∑u ∈ V (G)f(u) over all such functions is called the Roman domination numberγR(G). We show thatγt(G)≤ γR(G) with equality if and only ifγt(G)=2γ(G), whereγ(G) is the domination number ofG. Moreover, we characterize the extremal graphs for some graph families. [ABSTRACT FROM AUTHOR]

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 FROM PUBLISHER]

An unfriendly partition is a partition of the vertices of a graph G = (V,E) into two sets, say Red R(V) and Blue B(V), such that every Red vertex has at least as many Blue neighbors as Red neighbors, and every Blue vertex has at least as many Red neighbors as Blue neighbors. We present three polynomial time, self-stabilizing algorithms for finding unfriendly partitions in arbitrary graphs G, or equivalently into two disjoint dominating sets. [ABSTRACT FROM AUTHOR]

We provide self-stabilizing algorithms to obtain and maintain a maximal matching, maximal independent set or minimal dominating set in a given system graph. They converge in linear rounds under a distributed or synchronous daemon. They can be implemented in an ad hoc network by piggy-backing on the beacon messages that nodes already use. [ABSTRACT FROM AUTHOR]

The paradigm of self-stabilization provides a mechanism to design efficient localized distributed algorithms that are proving to be essential for modern day large networks of sensors. We provide self-stabilizing algorithms (in the shared-variable ID-based model) for three graph optimization problems: a minimal total dominating set (where every node must be adjacent to a node in the set) and its generalizations, a maximal k-packing (a set of nodes where every pair of nodes are more than distance k apart), and a maxima! strong matching (a collection of totally disjoint edges). [ABSTRACT FROM AUTHOR]

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. Distributed algorithms that reach a legitimate state, starting from any illegitimate state, are called self-stabilizing. 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. [4] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. The motivation of k-forward numberings is to obtain new s-s graph coloring algorithms. 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 [13], 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. [ABSTRACT FROM AUTHOR]

In the state-based self-stabilizing algorithmic paradigm for distributed computing, each node has only a local view of the system (seeing its neighbors' states), yet in a finite amount of time the system converges to a global state satisfying some desired property. In this paper we introduce a general mechanism that allows a node to act only on correct distance-two knowledge, provided there are IDs. We then apply the mechanism to graph problems in the areas of coloring and domination. For example, we obtain an algorithm for maximal 2-packing which is guaranteed to stabilize In polynomial moves under a central dáemon. [ABSTRACT FROM AUTHOR]