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.     

Independent domination in subcubic graphs of girth at least six

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$. The independent domination number, $i\left(G\right)$, of $G$ is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if $G$ is a bipartite, cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$. We show that the bipartite condition can be relaxed, and prove that if $G$ is a cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$.     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.     

Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs

A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ _tc (G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ _tc (G) + γ _tc ($ \bar G $ \bar G ), and characterize the extremal graphs achieving these bounds.     

Upper total domination in claw‐free 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 (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ_t(G). We establish bounds on Γ_t(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

Connected domination of regular graphs

A dominating setD of a graph G is a subset of V(G) such that for every vertex v∈V(G), either v∈D or there exists a vertex u∈D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.     

树的3-彩虹控制数的上界

对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界.     

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     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

An upper bound for domination number of 5-regular graphs

Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n.     

Efficient algorithms for Roman domination on some classes of graphs

A Roman dominating function of a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=∑_x∈Vf(x), and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of -free graphs and graphs with a d-octopus.     

A note on the independent domination number in graphs

We obtain an upper bound for the independent domination number of a graph in terms of the domination number and maximum degree.     

A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.