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 (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]

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]

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]

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]