Tight bounds for eternal dominating sets in graphs

The eternal domination number of a graph is the number of guards needed at vertices of the graph to defend the graph against any sequence of attacks at vertices. We consider the model in which at most one guard can move per attack and a guard can move across at most one edge to defend an attack. We prove that there are graphs G for which , where γ_∞(G) is the eternal domination number of G and α(G) is the independence number of G. This matches the upper bound proved by Klostermeyer and MacGillivray.     

Maximum graphs with a unique minimum dominating set

We present a conjecture on the maximum number of edges of a graph that has a unique minimum dominating set. We verify our conjecture for some special cases and prove a weakened version of this conjecture in general.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

构建最小k 重控制集的概率算法

点集D ⊆ V (G) 称为图G 的k 重控制集, 如果D 满足V (G) - D 中任意结点在D 中至少有k 个邻居. 在无线网络中, 最小k 重控制集(MkDS) 用以构建健壮的虚拟骨干网. 构建虚拟骨干网是无线网络中最基本也是最重要的问题. 在本文中, 我们提出一种快速的分布式概率算法来构建k重控制集. 我们构建的k 重控制集的期望大小不超过最优解的O(k²) 倍. 算法的运行时间复杂度为O((Δ logΔ+log log n)n),其中Δ = max{|D(p)|}, D(p) 是以p 为中心半径为1 的圆盘中的结点, 最大值的比较范围是给定集合中所有的p 点.     

Independent dominating sets and hamiltonian cycles

A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007     

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 fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

Two sufficient conditions for dominating cycles

A cycle C of a graph G is dominating if each component of is edgeless. In the paper, we will give two sufficient conditions for each longest cycle of a 3‐connected graph to be a dominating cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Block graphs with unique minimum dominating sets

For any graph G a set D of vertices of G is a dominating set, if every vertex vV(G)−D has at least one neighbor in D. The domination number γ(G) is the smallest number of vertices in any dominating set. In this paper, a characterization is given for block graphs having a unique minimum dominating set. With this result, we generalize a theorem of Gunther, Hartnell, Markus and Rall for trees.     

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.     

Vertices contained in every minimum dominating set of a tree

In this article we begin the study of the vertex subsets of a graph G which consist of the vertices contained in all, or in no, respectively, minimum dominating sets of G. We characterize these sets for trees, and also obtain results on the vertices contained in all minimum independent dominating sets of trees. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 163‐177, 1999     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

Finding a minimum independent dominating set in a permutation graph

We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log²n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n³)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph.     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

On the maximum number of minimum dominating sets in forests

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^{\gamma }$ minimum dominating sets. Bień gave a counterexample, which allows us to construct forests with domination number $\gamma$ and $2.0598^{\gamma }$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^{\gamma }$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha -1}+1$ maximum independent sets.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

Long cycles in critical graphs

It is shown that any k‐critical graph with n vertices contains a cycle of length at least , improving a previous estimate of Kelly and Kelly obtained in 1954. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 193–196, 2000     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.