Some properties onf-edge covered critical graphs

LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ _fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δ_f or δ _f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ _fc (G)=δ _f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ _fc (G + e) > ÷ _fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ _f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ _f + 1 vertices which are all δ _f -vertex inG.     

Unique response Roman domination in graphs

A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V₀,V₁,V₂) of V(G), where V_i={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V₀ implies |N(x)∩V₂|≤1 and x∈V₁∪V₂ implies that |N(x)∩V₂|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by u_R(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter.     

A note on Roman domination in 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 of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

On the bondage number of middle graphs

Let G = (V (G),E(G)) be a simple graph. A subset S of V (G) is a dominating set of G if, for any vertex v ∈ V (G) — S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimal dominating set of G. There are several types of domination parameters depending upon the nature of domination and the nature of dominating set. These parameters are bondage, reinforcement, strong-weak domination, strong-weak bondage numbers. In this paper, we first investigate the strong-weak domination number of middle graphs of a graph. Then several results for the bondage, strong-weak bondage number of middle graphs are obtained.     

Roman dominating influence parameters

A function f:V(G)→{0,1,2} is a Roman dominating function for a graph G=(V,E) if for every vertex v with f(v)=0, there exists a vertex w∈N(v) with f(w)=2. Emperor Constantine had the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and traveling. Each vertex with no army must have a neighboring vertex with a traveling army. Stationary armies then dominate their own vertices, and a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the traveling army. In this paper, we introduce Roman dominating influence parameters in which the interest is in dominating each vertex exactly once.     

Roman Domination Dot-critical Graphs

A Roman dominating function on a graph 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))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.     

Radial trees

A broadcast on a graph G is a function such that for each v∈V, f(v)≤e(v) (the eccentricity of v). The broadcast number of G is the minimum value of ∑_v∈Vf(v) among all broadcasts f for which each vertex of G is within distance f(v) from some vertex v having f(v)≥1. This number is bounded above by the radius of G as well as by its domination number. Graphs for which the broadcast number is equal to the radius are called radial; the problem of characterizing radial trees was first discussed in [J. Dunbar, D. Erwin, T. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. (154) (2006) 59-75].We provide a characterization of radial trees as well as a geometrical interpretation of our characterization.     

Broadcasts and domination in trees

A broadcast on a graph G is a function f:V→Z⁺∪{0}. The broadcast number of G is the minimum value of ∑_v∈Vf(v) among all broadcasts f for which each vertex of G is within distance f(v) from some vertex v with f(v)≥1. This number is bounded above by the radius and the domination number of G. We show that to characterize trees with equal broadcast and domination numbers it is sufficient to characterize trees for which all three of these parameters coincide.     

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.     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices 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 on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

Secure domination critical graphs

A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈V_G−X is adjacent to a vertex v∈X such that (X−{v})∪{u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by γ_s(G). We are interested in the effect of edge removal on γ_s(G), and characterize γ_s-ER-critical graphs, i.e. graphs for which γ_s(G−e)>γ_s(G) for any edge e of G, bipartite γ_s-ER-critical graphs and γ_s-ER-critical trees.     

Hexavalent (G,s)-transitive graphs

Let X be a finite simple undirected graph with a subgroup G of the full automorphism group Aut(X). Then X is said to be (G, s)-transitive for a positive integer s, if G is transitive on s-arcs but not on (s + 1)-arcs, and s-transitive if it is (Aut(X), s)-transitive. Let G _v be a stabilizer of a vertex v ∈ V (X) in G. Up to now, the structures of vertex stabilizers G _v of cubic, tetravalent or pentavalent (G, s)-transitive graphs are known. Thus, in this paper, we give the structure of the vertex stabilizers G _v of connected hexavalent (G, s)-transitive graphs.     

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.     

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph 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){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.     

Global italian domination in graphs

Abstract

An Italian dominating function (IDF) on a graph G = (V, E) is a function f: V → {0, 1, 2} satisfying the condition that for every vertex v ∈ V (G) with f (v) = 0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to at least two vertices assigned 1. The weight of an IDF f is the value ∑_v∈V(G) f (v). The Italian domination number of a graph G, denoted by γ_I (G), is the minimum weight of an IDF on G. An IDF f on G is called a global Italian dominating function (GIDF) on G if f is also an IDF on the complement ? of G. The global Italian domination number of G, denoted by γ_gI (G), is the minimum weight of a GIDF on G. In this paper, we initiate the study of the global Italian domination number and we present some strict bounds for the global Italian domination number. In particular, we prove that for any tree T of order n ≥ 4, γ_gI (T) ≤ γ_I (T) + 2 and we characterize all trees with γ_gI (T) = γ_I (T) + 2 and γ_gI (T) = γ_I (T) + 1.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Characterizations of trees with equal domination parameters

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set, if every vertex not in S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a restrained dominating set of G. A set S ⊆ V is a weak dominating set of G if, for every u in V − S, there exists a v ∈ S such that uv ∈ E and deg u ≥ deg v. The weak domination number of G, denoted by γ_w(G), is the minimum cardinality of a weak dominating set of G. In this article, we provide a constructive characterization of those trees with equal independent domination and restrained domination numbers. A constructive characterization of those trees with equal independent domination and weak domination numbers is also obtained. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 142–153, 2000