Power domination in graphs

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 domination problem in graphs. In 1998, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined 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 power domination number γ_P(G) of a graph G is the minimum cardinality of a power dominating set of G. In this paper, we present upper bounds on the power domination number for a connected graph with at least three vertices and a connected claw-free cubic graph in terms of their order. The extremal graphs attaining the upper bounds are also characterized.     

Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Set domination in graphs

Let G = (V, E) be a connected graph. A set D ? V is a set-dominating set (sd-set) if for every set T ? V ? D, there exists a nonempty set S ? D such that the subgraph 〈S ∪ T〉 induced by S ∪ T is connected. The set-domination number γ_s(G) of G is the minimum cardinality of a sd-set. In this paper we develop properties of this new parameter and relate it to some other known domination parameters.     

Line domination in graphs

A setS of lines is a line dominating set if every line not inS is adjacent to some line ofS. The line domination number of a graph is the cardinality of a minimum line dominating set. In this paper we study the line dominating sets and obtain bounds for the line domination number. Also, Nordhaus-Gaddum type results are obtained for the line domination number and the line domatic number.     

Vertex-edge domination in graphs

Aequationes mathematicae - We establish that for any connected graph G of order $$n \ge 6$$ , a minimum vertex-edge dominating set of G has at most n/3 vertices, thus affirmatively answering the...     

Minus total domination in graphs

A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ _t ⁻(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ _t ⁻(G).     

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{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(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

On restricted domination in graphs

The k-restricted domination number of a graph G is the minimum number d _k such that for any subset U of k vertices of G, there is a dominating set in G including U and having at most d _k vertices. Some new upper bounds in terms of order and degrees for this number are found.      

Total domination in inflated graphs

The inflation $G_I$ of a graph $G$ is obtained from $G$ by replacing every vertex $x$ of degree $d\left(x\right)$ by a clique $X=K_{d\left(x\right)}$ and each edge $xy$ by an edge between two vertices of the corresponding cliques $X$ and $Y$ of $G_I$ in such a way that the edges of $G_I$ which come from the edges of $G$ form a matching of $G_I$. A set $S$ of vertices in a graph $G$ is a total dominating set, abbreviated TDS, of $G$ if every vertex of $G$ is adjacent to a vertex in $S$. The minimum cardinality of a TDS of $G$ is the total domination number ${\gamma }_t\left(G\right)$ of $G$. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if $G$ is a connected graph of order $n\ge 2$, then ${\gamma }_t\left(G_I\right)\ge 2n/3$, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of $G$ to be at least $2$, then we show that ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if $G$ has a perfect matching. If we increase the minimum degree requirement of $G$ to be at least $3$, then we show ${\gamma }_t\left(G_I\right)\ge n$, with equality if and only if every minimum TDS of $G_I$ is a perfect total dominating set of $G_I$, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.     

Secure domination critical graphs

A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈V_G−X is adjacent to a vertex v∈X such that (X−{v})∪{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by γ_s(G). We are interested in the effect of edge removal on γ_s(G), and characterize γ_s-ER-critical graphs, i.e. graphs for which γ_s(G−e)>γ_s(G) for any edge e of G, bipartite γ_s-ER-critical graphs and γ_s-ER-critical trees.     

Minus domination in small-degree graphs

Minus domination in graphs is a variant of domination where the vertices must be labeled −1,0,+1 such that the sum of labels in each N[v] is positive. (As usual, N[v] means the set containing v together with its neighbors.) The minus domination number γ⁻ is the minimum total sum of labels that can be achieved. In this paper we prove linear lower bounds for γ⁻ in graphs either with Δ⩽3, or with Δ⩽4 but without vertices of degree 2. The central section is concerned with complexity results for Δ⩽4: We show that computing γ⁻ is NP-hard and MAX SNP-hard there, but that γ⁻ can be approximated in linear time within some constant factor. Finally, our approach also applies to signed domination (where the labels are −1,+1 only) in small-degree graphs.     

Global italian domination in graphs

Abstract

An Italian dominating function (IDF) on a graph G = (V, E) is a function f: V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V (G) with f (v) = 0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1. The weight of an IDF f is the value ∑_v∈V(G) f (v). The Italian domination number of a graph G, denoted by γ_I (G), is the minimum weight of an IDF on G. An IDF f on G is called a global Italian dominating function (GIDF) on G if f is also an IDF on the complement ? of G. The global Italian domination number of G, denoted by γ_gI (G), is the minimum weight of a GIDF on G. In this paper, we initiate the study of the global Italian domination number and we present some strict bounds for the global Italian domination number. In particular, we prove that for any tree T of order n ≥ 4, γ_gI (T) ≤ γ_I (T) + 2 and we characterize all trees with γ_gI (T) = γ_I (T) + 2 and γ_gI (T) = γ_I (T) + 1.