Restrained domination in cubic graphs

Let G=(V,E) be a graph. 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 restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then g_r(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then g_r(G) ￡ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ _r (G)=γ(G).     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

Total restrained domination in claw-free graphs

A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ _tr (G)=n. Also, we show that γ _tr (G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.     

Paired versus double domination in K 1,r -free graphs

A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set in G. A subset S?V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ _×2(G). A claw-free graph is a graph that does not contain K _1,3 as an induced subgraph. Chellali and Haynes (Util. Math. 67:161–171, 2005) showed that for every claw-free graph G, we have γ _pr(G)≤γ _×2(G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K _1,r as an induced subgraph, then $\gamma_{\mathrm{pr}}(G)\le ( \frac{2r^{2}-6r+6}{r(r-1)} )\gamma_{\times2}(G)$ .     

On the total domination subdivision number in some classes of graphs

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some 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_gt(G)\mathrm {sd}_{\gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sd_gt(G) ￡ g_t(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1 for some classes of graphs.     

On the power domination number of the generalized Petersen 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. Following a set of rules for power system monitoring, 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. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

The total {k}-domatic number of a graph

For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑ _u∈N(v) f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f ₁,f ₂,…,f _d } of total {k}-dominating functions on G with the property that ?_i=1^df_i(v) ￡ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by d_t^{k}(G)d_{t}^{\{k\}}(G). Note that d_t^{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d _t (G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for d_t^{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d _t (G) are immediate consequences of our results.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Upper paired-domination in claw-free graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_pr(G). We establish bounds on Γ_pr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_pr(G)≤4n/5 if δ=1 and n≥3, Γ_pr(G)≤3n/4 if δ=2 and n≥6, and Γ_pr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_pr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_pr(G)=3n/4 are characterized.     

Perfect matchings in paired domination vertex critical graphs

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ _pr (G), is the minimum cardinality of a paired dominating set of?G. A?graph with no isolated vertex is called paired domination vertex critical, or briefly γ _pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ _pr (G?v)<γ _pr (G). A?γ _pr -critical graph G is said to be k-γ _pr -critical if γ _pr (G)=k. In this paper, we firstly show that every 4-γ _pr -critical graph of even order has a perfect matching if it is K _1,5-free and every 4-γ _pr -critical graph of odd order is factor-critical if it is K _1,5-free. Secondly, we show that every 6-γ _pr -critical graph of even order has a perfect matching if it is K _1,4-free.     

Which trees have a differentiating-paired dominating set?

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩S≠N[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating set.     

Galaxy cutsets in graphs

Given a network G=(V,E), we say that a subset of vertices S⊆V has radius r if it is spanned by a tree of depth at most r. We are interested in determining whether G has a cutset that can be written as the union of k sets of radius r. This generalizes the notion of k-vertex connectivity, since in the special case r=0, a set spanned by a tree of depth at most r is a single vertex.     

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

On the construction of k-connected m-dominating sets in wireless networks

Connected dominating sets (CDS) that serve as a virtual backbone are now widely used to facilitate routing in wireless networks. A k-connected m-dominating set (kmCDS) is necessary for fault tolerance and routing flexibility. In order to construct a kmCDS with the minimum size, some approximation algorithms have been proposed in literature. However, the proposed algorithms either only consider some special cases where k=1, 2 or k≤m, or not easy to implement, or cannot provide performance ratio. In this paper, we propose a centralized heuristic algorithm, CSAA, which is easy to implement, and two distributed algorithms, DDA and DPA, which are deterministic and probabilistic methods respectively, to construct a kmCDS for general k and m. Theoretical analysis and simulation results indicate that our algorithms are efficient and effective.     

Near automorphisms of trees with small total relative displacements

For a permutation f of the vertex set V(G) of a connected graph G, let δ _f (x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ _f (G) of G with respect to f to be the sum of δ _f (x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ _f (G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.