Search

Let m G ( I ) denote the number of Laplacian eigenvalues of a graph G in an interval I . Our main result is that for graphs having domination number γ , m G [ 0 , 1 ) ≤ γ , improving existing bounds in the literature. For many graphs, m G [ 0 , 1 ) = γ , or m G [ 0 , 1 ) = γ − 1 . [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 theorem of Ore [20] states that if D is a minimal dominating set in a graph G = ( V , E ) having no isolated nodes, then V − D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B . We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7] , yielding running times of O ( n 2 m ) . [ABSTRACT FROM AUTHOR]

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. [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]

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]

Abstract: Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general transformation for constructing self-stabilizing algorithms which utilize distance- knowledge. Our transformation has both a slowdown and space overhead in , and might be thought of as a distance- resource allocation algorithm. Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. These results can be generalized to efficiently find maximal -sets, for properties which we call local monotonic. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information. [Copyright &y& Elsevier]

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]

For a graph property P, in particular maximal independence, minimal domination and maximal irredundance, we introduce iterated P-colorings of graphs. The six graph parameters arising from either maximizing or minimizing the number of colors used for each property, are related by an inequality chain, and in this paper we initiate the study of these parameters. We relate them to other well-studied parameters like chromatic number, give alternative characterizations, find graph classes where they differ by an arbitrary amount, investigate their monotonicity properties, and look at algorithmic issues. [Copyright &y& Elsevier]

A (proper) k-coloring of a graph G is a partition Π={V1,V2,…,Vk} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈Vi is called a Grundy vertex if v is adjacent to at least one vertex in color class Vj, for every j, j. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982. [Copyright &y& Elsevier]

Motivated by an article by Ian Stewart (Defend the Roman Empire!, Scientific American, Dec. 1999, pp. 136–138), we explore a new strategy of defending the Roman Empire that has the potential of saving the Emperor Constantine the Great substantial costs of maintaining legions, while still defending the Roman Empire. In graph theoretic terminology, let G=(V,E) be a graph and let f be a function f : V→{0,1,2}. A vertex u with f(u)=0 is said to be undefended with respect to f if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u)=0 is adjacent to a vertex v with f(v)>0 such that the function f′ : V→{0,1,2}, defined by f′(u)=1, f′(v)=f(v)−1 and f′(w)=f(w) if w∈V−{u,v}, has no undefended vertex. The weight of f is w(f)=∑v∈Vf(v). The weak Roman domination number, denoted γr(G), is the minimum weight of a WRDF in G. We show that for every graph G, γ(G)⩽γr(G)⩽2γ(G). We characterize graphs G for which γr(G)=γ(G) and we characterize forests G for which γr(G)=2γ(G). [Copyright &y& Elsevier]

For graphs G and H, a set S⊆V(G) is an H-forming set of G if for every v∈V(G)−S, there exists a subset R⊆S, where |R|=|V(H)|−1, such that the subgraph induced by R∪{v} contains H as a subgraph (not necessarily induced). The minimum cardinality of an H-forming set of G is the H-forming number γ{H}(G). The H-forming number of G is a generalization of the domination number γ(G) because γ(G)=γ{P2}(G). We show that γ(G)⩽γ{P3}(G)⩽γt(G), where γt(G) is the total domination number of G. For a nontrivial tree T, we show that γ{P3}(T)=γt(T). We also define independent P3-forming sets, give complexity results for the independent P3-forming problem, and characterize the trees having an independent P3-forming set. [Copyright &y& Elsevier]

For a graph G = ( V , E ) and a set S ⊆ V , the boundary of S is the set of vertices in V ∖ S that have a neighbor in S . A non-empty set S ⊆ V is a distribution center if for every vertex v in the boundary of S , v is adjacent to a vertex in S , say u , where u has at least as many neighbors in S as v has in V ∖ S . The distribution center number of a graph G is the minimum cardinality of a distribution center of G . We introduce distribution centers as graph models for supply–demand type distribution. We determine the distribution center number for selected families of graphs and give bounds on the distribution center number for general graphs. Although not necessarily true for general graphs, we show that for trees the domination number and the maximum degree are upper bounds on the distribution center number. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) , we consider placing a variable number of pebbles on the vertices of V . A pebbling move consists of deleting two pebbles from a vertex u ∈ V and placing one pebble on a vertex v adjacent to u . We seek an initial placement of a minimum total number of pebbles on the vertices in V , so that no vertex receives more than some positive integer t pebbles and for any given vertex v ∈ V , it is possible, by a sequence of pebbling moves, to move at least one pebble to v . We relate this minimum number of pebbles to several other well-studied parameters of a graph G , including the domination number, the optimal pebbling number, and the Roman domination number of G . [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a graph with vertex set V and edge set E . A vertex v ∈ V v e -dominates every edge incident to it as well as every edge adjacent to these incident edges. The vertex–edge degree of a vertex v is the number of edges v e -dominated by v . Similarly, an edge e = u v e v -dominates the two vertices u and v incident to it, as well as every vertex adjacent to u or v . The edge–vertex degree of an edge e is the number of vertices e v -dominated by edge e . In this paper we introduce these types of degrees and study their properties. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) , a double Roman dominating function is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v must have at least one neighbor with f ( w ) ≥ 2 . The weight of a double Roman dominating function f is the sum f ( V ) = ∑ v ∈ V f ( v ) , and the minimum weight of a double Roman dominating function on G is the double Roman domination number of G . We initiate the study of double Roman domination and show its relationship to both domination and Roman domination. Finally, we present an upper bound on the double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G = ( V , E ) , a Roman { 2 } -dominating function f : V → { 0 , 1 , 2 } has the property that for every vertex v ∈ V with f ( v ) = 0 , either v is adjacent to a vertex assigned 2 under f , or v is adjacent to least two vertices assigned 1 under f . The weight of a Roman { 2 } -dominating function is the sum ∑ v ∈ V f ( v ) , and the minimum weight of a Roman { 2 } -dominating function f is the Roman { 2 } -domination number. First, we present bounds relating the Roman { 2 } -domination number to some other domination parameters. In particular, we show that the Roman { 2 } -domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman { 2 } -domination is NP-complete, even for bipartite graphs. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RDF) on a graph G is a function f : V (G) → {0,1,2} satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V) = ... f(v), and the minimum weight of a Roman dominating function f is the Roman domination number γR(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum degree Δ, γR(G)≥ ... and iR(G) ≥ i(G) + γ(G)/Δ, where γ(G) and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for γR(G) and compare our two new bounds on γR(G) with some known lower bounds. [ABSTRACT FROM AUTHOR]

We mainly study two related dominating functions, namely, the weak Roman and 2-rainbow dominating functions. We show that for all graphs, the weak Roman domination number is bounded above by the 2-rainbow domination number. We present bounds on the weak Roman domination number and the secure domination number in terms of the total domination number for specific families of graphs, and we show that the 2-rainbow domination number is bounded below by the total domination number for trees and for a subfamily of cactus graphs. [ABSTRACT FROM AUTHOR]

Abstract: A subset in a graph is a -set if, for every vertex , for non-negative integers and , that is, every vertex is adjacent to at least but not more than vertices in . In this paper, we focus on small and , and relate the concept of -sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and -dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph , the restrained domination number is equal to the domination number of . [Copyright &y& Elsevier]

A set S ⊆ V is a dominating set of a graph G = (V,E) if every vertex in V -S is adjacent to at least one vertex in S. The domination number γ(G) of G equals the minimum cardinality of a dominating set S in G; we say that such a set S is a γ-set. In this paper we consider the family of all γ-sets in a graph G and we define the γ- graph G(γ) = (V (γ),E(γ)) of G to be the graph whose vertices V (γ) correspond 1-to-1 with the γ-sets of G, and two γ-sets, say D1 and D2, are adjacent in E(γ) if there exists a vertex v ∪ D1 and a vertex w ∈ D1 such that v is adjacent to w and D1 = D2 - {w} ∪ {v}, or equivalently, D2 = D1 -{v}∪{w}. In this paper we initiate the study of γ-graphs of graphs. [ABSTRACT FROM AUTHOR]

Abstract: We present a collection of new structural, algorithmic, and complexity results for matching problems of two types. The first problem involves the computation of -maximal matchings, where a matching is -maximal if it admits no augmenting path with vertices. The second involves finding a maximal set of vertices that is matchable — comprising one side of the edges in some matching. Among our results, we prove that the minimum cardinality of a 2-maximal matching is at most the minimum cardinality of a maximal matchable set, with equality attained for triangle-free graphs. We show that the parameters and are NP-hard to compute in bipartite and chordal graphs, but can be computed in linear time on a tree. Finally, we also give a simple linear-time algorithm for finding a 3-maximal matching, a consequence of which is a simple linear-time -approximation algorithm for the maximum-cardinality matching problem in a general graph. [Copyright &y& Elsevier]

Abstract: The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k. We present an dynamic programming algorithm for computing the maximum number of vertices that can be dominated using dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems. [Copyright &y& Elsevier]

Abstract: Let be a graph. A set is a defensive alliance if for every . Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. Necessary and sufficient conditions for a set to be secure are determined. [Copyright &y& Elsevier]

Abstract: A coloring of a graph is a partition of into independent sets or color classes. A vertex is a Grundy vertex if it is adjacent to at least one vertex in each color class for every . A coloring is a partial Grundy coloring if every color class contains at least one Grundy vertex, and the partial Grundy number of a graph is the maximum number of colors in a partial Grundy coloring. We derive a natural upper bound on this parameter and show that graphs with sufficiently large girth achieve equality in the bound. In particular, this gives a linear-time algorithm to determine the partial Grundy number of a tree. [Copyright &y& Elsevier]

Abstract: For a graph property , we define a -matching as a set M of disjoint edges such that the subgraph induced by the vertices incident to M has property . Previous examples include strong/induced matchings and uniquely restricted matchings. We explore the general properties of -matchings, but especially the cases where is the property of being acyclic or the property of being disconnected. We consider bounds on and the complexity of the maximum cardinality of a -matching and the minimum cardinality of a maximal -matching. [Copyright &y& Elsevier]

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]

In a graph or network G = (V, E), a set S C V is k-dependent if no node in S has more than k neighbors in S. We show that for each k > 0 there is a self-stabilizing algorithm that identifies a maximal k-dependent set, and stabilizes in O(kn) moves, where n is the number of nodes. An interesting by-product of our paper is the new result that in any graph there exists a set that is both maximal k-dependent and minimal (k + 1)-dominating. The set selected by our algorithm, in fact, has this property. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is called a total irredundant set if, for each vertex v in G, v or one of its neighbors has no neighbor in S−{v}. We investigate the minimum and maximum cardinalities of maximal total irredundant sets. [Copyright &y& Elsevier]

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 γ[sub 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 γ[sub P](T) in trees T. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A (closed) neighborhood-restricted [ ≤ 2 ] -coloring of a graph G is an assignment of colors to the vertices of G such that no more than two colors are assigned in any closed neighborhood, that is, for every vertex v in G , the vertex v and its neighbors are in at most two different color classes. The [ ≤ 2 ] -achromatic number is defined as the maximum number of colors in any [ ≤ 2 ] -coloring of G . We study the [ ≤ 2 ] -achromatic number. In particular, we improve a known upper bound and characterize the extremal graphs for some other known bounds. [ABSTRACT FROM AUTHOR]

Abstract: For a graph , a non-empty set is a defensive alliance if for every vertex in , has at most one more neighbor in than it has in , and is an offensive alliance if for every that has a neighbor in , has more neighbors in than in . A powerful alliance is both defensive and offensive. We initiate the study of powerful alliances in graphs. [Copyright &y& Elsevier]

Abstract: We say that a function is a broadcast if for every vertex , , where denotes the diameter of G and denotes the eccentricity of . The cost of a broadcast is the value . In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts. [Copyright &y& Elsevier]

A Roman dominating function on a graph G=(V,E) is a function f : V→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V)=∑u∈Vf(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper, we study the graph theoretic properties of this variant of the domination number of a graph. [Copyright &y& Elsevier]