Domination with exponential decay

Let G be a graph and S⊆V(G). For each vertex u∈S and for each v∈V(G)−S, we define to be the length of a shortest path in 〈V(G)−(S−{u})〉 if such a path exists, and ∞ otherwise. Let v∈V(G). We define if v⁄∈S, and w_S(v)=2 if v∈S. If, for each v∈V(G), we have w_S(v)≥1, then S is an exponential dominating set. The smallest cardinality of an exponential dominating set is the exponential domination number, γ_e(G). In this paper, we prove: (i) that if G is a connected graph of diameter d, then γ_e(G)≥(d+2)/4, and, (ii) that if G is a connected graph of order n, then .     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

A better approximation algorithm for the budget prize collecting tree problem

Given an undirected graph G=(V,E), an edge cost c(e)?0 for each edge e∈E, a vertex prize p(v)?0 for each vertex v∈V, and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to find a subtree T′=(V′,E′) that maximizes , subject to . We present a (4+ε)-approximation algorithm.     

A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.     

Asymptotic stability at infinity for differentiable vector fields of the plane

Let be a differentiable (but not necessarily C¹) vector field, where σ>0 and . Denote by R(z) the real part of z∈C. If for some ?>0 and for all , no eigenvalue of DpX belongs to , then: (a) for all , there is a unique positive semi-trajectory of X starting at p; (b) it is associated to X, a well-defined number I(X) of the extended real line [−∞,∞) (called the index of X at infinity) such that for some constant vector v∈R² the following is satisfied: if I(X) is less than zero (respectively greater or equal to zero), then the point at infinity ∞ of the Riemann sphere R²∪{∞} is a repellor (respectively an attractor) of the vector field X+v.     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

Variable neighborhood search for extremal graphs. 23. On the Randi? index and the chromatic number

Let G=(V,E) be a simple graph with vertex degrees d₁,d₂,…,d_n. The Randi? index R(G) is equal to the sum over all edges (i,j)∈E of weights . We prove several conjectures, obtained by the system AutoGraphiX, relating R(G) and the chromatic number χ(G). The main result is χ(G)≤2R(G). To prove it, we also show that if v∈V is a vertex of minimum degree δ of G, G−v the graph obtained from G by deleting v and all incident edges, and Δ the maximum degree of G, then .     

The ω-limit set of a graph map

Let G be a graph and be continuous. Denote by P(f), , ω(f) and Ω(f) the set of periodic points, the closure of the set of periodic points, ω-limit set and non-wandering set of f, respectively. In this paper we show that: (1) v∈ω(f) if and only if v∈P(f) or there exists an open arc L=(v,w) contained in some edge of G such that every open arc U=(v,c)⊂L contains at least 2 points of some trajectory; (2) v∈ω(f) if and only if every open neighborhood of v contains at least r+1 points of some trajectory, where r is the valence of v; (3) ; (4) if , then x has an infinite orbit.     

Precoloring extension for 2-connected graphs with maximum degree three

Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K₄ then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set.     

The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

The signed star domination numbers of the Cartesian product graphs

Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where E_G(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γ_SS(G). In this paper, a sharp upper bound of γ_SS(G×H) is presented.     

Long paths with endpoints in given vertex-subsets of graphs

Let G=(V,E) be a connected graph of order n, t a real number with t?1 and M⊆V(G) with . In this paper, we study the problem of some long paths to maintain their one or two different endpoints in M. We obtain the following two results: (1) for any vertex v∈V(G), there exists a vertex u∈M and a path P with the two endpoints v and u to satisfy , , d_G(u)+1-t}; (2) there exists either a cycle C to cover all vertices of M or a path P with two different endpoints u₀ and u_p in M to satisfy , where .     

Bernstein widths of Hardy-type operators in a non-homogeneous case

Let I=[a,b]⊂R, let 1<p?q<∞, let u and v be positive functions with u∈Lp^′(I), v∈Lq(I) and let be the Hardy-type operator given by

     

Broadcasts in graphs

We say that a function f:V→{0,1,…,diam(G)} is a broadcast if for every vertex v∈V, f(v)?e(v), where diam(G) denotes the diameter of G and e(v) denotes the eccentricity of v. The cost of a broadcast is the value . In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.     

Heteroclinic solutions for a class of the second order Hamiltonian systems

We shall be concerned with the existence of heteroclinic orbits for the second order Hamiltonian system , where q∈Rn and V∈C¹(R×Rn,R), V?0. We will assume that V and a certain subset M⊂Rn satisfy the following conditions. M is a set of isolated points and #M?2. For every sufficiently small ε>0 there exists δ>0 such that for all (t,z)∈R×Rn, if d(z,M)?ε then −V(t,z)?δ. The integrals , z∈M, are equi-bounded and −V(t,z)→∞, as |t|→∞, uniformly on compact subsets of Rn?M. Our result states that each point in M is joined to another point in M by a solution of our system.     

Upper signed domination number

Let G=(V,E) be a graph. A signed dominating function on G is a function f:V→{-1,1} such that for each v∈V, where N[v] is the closed neighborhood of v. The weight of a signed dominating function f is . A signed dominating function f is minimal if there exists no signed dominating function g such that g≠f and g(v)?f(v) for each v∈V. The upper signed domination number of a graph G, denoted by Γ_s(G), equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for Γ_s(G) in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in [O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287-293] and [C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193-197], respectively.     

Small alliances in a weighted graph

We extend the notion of a defensive alliance to weighted graphs. Let (G,w) be a weighted graph, where G is a graph and w be a function from V(G) to the set of positive real numbers. A non-empty set of vertices S in G is said to be a weighted defensive alliance if ∑_{x∈NG(v)∩S}w(x)+w(v)≥∑_{x∈NG(v)−S}w(x) holds for every vertex v in S. Fricke et al. (2003) [3] have proved that every graph of order n has a defensive alliance of order at most . In this note, we generalize this result to weighted defensive alliances. Let G be a graph of order n. Then we prove that for any weight function w on V(G), (G,w) has a defensive weighted alliance of order at most . We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) [3].