Total domination critical and stable graphs upon edge removal

A set S of vertices in a graph G is a total dominating set of G 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. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.     

Total domination stable graphs upon edge addition

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. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs.     

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.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

A survey of selected recent results on total domination in graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. In this paper, we offer a survey of selected recent results on total domination in graphs.     

A sharp upper bound on algebraic connectivity using domination number

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.     

Total domination subdivision numbers of trees

A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number γ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt(G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1?sd_γt(T)?3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3.     

On the Independent Domination Number of Regular Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. In this paper, we consider questions about independent domination in regular graphs.     

On the bondage number of middle graphs

Let G = (V (G),E(G)) be a simple graph. A subset S of V (G) is a dominating set of G if, for any vertex v ∈ V (G) — S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimal dominating set of G. There are several types of domination parameters depending upon the nature of domination and the nature of dominating set. These parameters are bondage, reinforcement, strong-weak domination, strong-weak bondage numbers. In this paper, we first investigate the strong-weak domination number of middle graphs of a graph. Then several results for the bondage, strong-weak bondage number of middle graphs are obtained.     

Domination versus disjunctive domination in graphs

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

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.     

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γ_tr(G) (γ_r(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P₃, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds.     

Properties of total domination edge-critical graphs

A set S of vertices in a graph G is a total dominating set of G 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 γ_t(G) of G. The graph G is total domination edge critical if for every edge e in the complement of G, γ_t(G+e)<γ_t(G). We call such graphs γ_tEC. Properties of γ_tEC graphs are established.     

On trees with total domination number equal to edge-vertex domination number plus one

An edge e∈E(G) dominates a vertex v∈V(G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D?V(G) is a total dominating set of G if every vertex of G has a neighbor in D. The total domination number of G is the minimum cardinality of a total dominating set of G. We characterize all trees with total domination number equal to edge-vertex domination number plus one.     

A note on power domination in grid 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 vertex covering and dominating set problems in graphs (see [T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, M.A. Henning, Power domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15(4) (2002) 519-529]). A set S of vertices is defined 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 is its power domination number. In this paper, we determine the power domination number of an n×m grid graph.     

Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

Bounds on Laplacian eigenvalues related to total and signed domination of graphs

A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

Total Domination in Graphs with Given Girth

A set S of vertices in a graph G without isolated vertices is a total dominating set of G 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 γ _t (G) of G. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g, then γ _t (G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs. Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.