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     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

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. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Average distances and distance domination numbers

Let k be a positive integer and G be a simple connected graph with order n. The average distance μ(G) of G is defined to be the average value of distances over all pairs of vertices of G. A subset D of vertices in G is said to be a k-dominating set of G if every vertex of V(G)−D is within distance k from some vertex of D. The minimum cardinality among all k-dominating sets of G is called the k-domination number γ_k(G) of G. In this paper tight upper bounds are established for μ(G), as functions of n, k and γ_k(G), which generalizes the earlier results of Dankelmann [P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21-35] for k=1.     

Irredundance in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K_d. We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G_I) − ir(G_I) can be arbitrarily large, IR(G_I) ≤ m(G) and IR(G_I) ≤ n²(G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143–154) and answer another open question. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 97–104, 1998     

A new domination conception

Let f be an integer valued function defined on the vertex set V(G) of a simple graph G. We call a subset D_f of V(G) a f-dominating set of G if |N(x, G) ∩ D_f| ≥ f(x) for all x ∈ V(G) — D_f, where N(x, G) is the set of neighbors of x. D_f is a minimum f-dominating set if G has no f-dominating set D′_f with |D_f| < |D_f|. If j, k ∈ N₀ = {0,1,2,…} with j ≤ k, then we define the integer valued function f_j,k on V(G) by . By μ_j,k(G) we denote the cardinality of a minimum f_j,k-dominating set of G. A set D ? V(G) is j-dominating if every vertex, which is not in D, is adjacent to at least j vertices of D. The j-domination number γ_j(G) is the minimum order of a j-dominating set in G. In this paper we shall give estimations of the new domination number μ_j,k(G), and with the help of these estimations we prove some new and some known upper bounds for the j-domination number. © 1993 John Wiley & Sons, Inc.     

Some bounds on the p-domination number in trees

Let p be a positive integer and G=(V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p-1. The minimum cardinality of a p-dominating set a of G is the p-domination number γ_p(G) and the maximum cardinality of a p-dependent set of G is the p-dependence number β_p(G). For every positive integer p?2, we show that for a bipartite graph G, γ_p(G) is bounded above by (|V|+|Y_p|)/2, where Y_p is the set of vertices of G of degree at most p-1, and for every tree T, γ_p(T) is bounded below by β_p-1(T). Moreover, we characterize the trees achieving equality in each bound.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

Further results on the lower bounds of mean color numbers

Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x₁,x₂,…,x_n such that x_i is contained in a K₃ of G[V_i] for i = 3,4,…,n, where V_i = {x₁,x₂,…,x_i}. This result improves two known results that μ(G) ≥ μ(O_n) where O_n is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Graph-theoretic parameters concerning domination,independence, and irredundance

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah Gwith p vertices and no isolated vertices, i(G) ≤ p-γ(G) + 1 - ?(p - γ(G))/γ(G)?.     

A Structure Preserving Generalization of Independence,Domination and Irredundance

Abstract

The now famous inequality chain ir≤γ≤i≤β ≤ Γ ≤ IR, where ir and IR denote the lower and upper irredundance numbers of a graph, γ and Γ the lower and upper domination numbers, i the independent domination number and β the independence number of a graph, may be seen as the culmination of a process by which we start with independence (a hereditary property of vertex sets); we characterize maximal independence by domination (a superhereditary property of vertex sets), and then characterize minimal domination by irredundance (again a hereditary property). In this paper we generalize independent, dominating and irredundant sets of a graph G to what we will call s-dominating, s-independent and s-irredundant functions (for s a positive integer), which are functions of the type f : V (G) → N, in such a way that the maximal 1-independent, the minimal 1- dominating and the maximal 1-irredundant functions are the characteristic functions of the maximal independent, the minimal dominating and the maximal irredundant sets of G respectively. In addition, we would want to preserve those properties of and relationships between independence, domination and irredundance needed to extend the inequality chain ir≤γ≤i≤β ≤ Γ ≤ IR to one for s-dominating, s-independent and s-irredundant functions by a process similar to that described above.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Generalized Rotation numbers

A rooted graph is a pair (G,x), where G is a simple undirected graph and x ∈ V(G). If G is rooted at x, its kth rotation number h_k (G,x) is the minimum number of edges in a graph F of order |G| + k such that for every v ∈ V(F) we can find a copy of G in F with the root vertex x at v. When k = 0, this definition reduces to that of the rotation number h(G,x), which was introduced in [“On Rotation Numbers for Complete Bipartite Graphs,” University of Victoria, Department of Mathematics Report No. DM-186-IR (1979)] by E.J. Cockayne and P.J. Lorimer and subsequently calculated for complete multipartite graphs. In this paper, we estimate the kth rotation number for complete bipartite graphs G with root x in the larger vertex class, thereby generalizing results of B. Bollobás and E.J. Cockayne [“More Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 6 (1982), pp. 403–411], J. Haviland [“Cliques and Independent Sets,” Ph. D. thesis, University of Cambridge (1989)], and J. Haviland and A. Thomason [“Rotation Numbers for Complete Bipartite Graphs,” Journal of Graph Theory, Vol. 16 (1992), pp. 61–71]. © 1993 John Wiley & Sons, Inc.     

The p-Bondage Number of Trees

Let p be a positive integer and G = (V, E) be a simple graph. A p-dominating set of G is a subset D  í  V{D\,{\subseteq}\, V} such that every vertex not in D has at least p neighbors in D. The p-domination number of G is the minimum cardinality of a p-dominating set of G. The p-bondage number of a graph G with (ΔG) ≥ p is the minimum cardinality among all sets of edges B í E{B\subseteq E} for which γ _p (G − B) > γ _p (G). For any integer p ≥ 2 and tree T with (ΔT) ≥ p, this paper shows that 1 ≤  b _p (T) ≤ (ΔT) − p + 1, and characterizes all trees achieving the equalities.     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

Dominating sets in triangulations on surfaces

Let G be a graph and let S?V(G). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S. We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most $\frac{n}{3}Let G be a graph and let S?V(G). We say that S is dominating in G if each vertex of G is in S or adjacent to a vertex in S. We show that every triangulation on the torus and the Klein bottle with n vertices has a dominating set of cardinality at most $\frac{n}{3}$. Moreover, we show that the same conclusion holds for a triangulation on any non‐spherical surface with sufficiently large representativity. These results generalize that for plane triangulations proved by Matheson and Tarjan (European J Combin 17 (1996), 565–568), and solve a conjecture by Plummer (Private Communication). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 17–30, 2010     

The rainbow connection of a graph is (at most) reciprocal to its minimum degree

An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010     

The ratio of the irredundance number and the domination number for block-cactus graphs

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998