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.     

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.     

On signed majority total domination in graphs

We initiate the study of signed majority total domination in graphs. Let G = (V, E) be a simple graph. For any real valued function f: V and S V, let . A signed majority total dominating function is a function f: V {–1, 1} such that f(N(v)) 1 for at least a half of the vertices v V. The signed majority total domination number of a graph G is = min{f(V): f is a signed majority total dominating function on G}. We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of .This research was supported by National Natural Science Foundation of China.     

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common 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 dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Total Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

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.     

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

Minus total domination in graphs

A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ _t ⁻(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ _t ⁻(G).     

An Erdös-Ko-Rado theorem for restricted signed sets

A restricted signed r-set is a pair （A, f）, where A lohtain in [n] = {1, 2,…, n} is an r-set and f is a map from A to [n] with f（i） ≠ i for all i ∈ A. For two restricted signed sets （A, f） and （B, g）, we define an order as （A, f） ≤ （B, g） if A C B and g｜A ： f A family .A of restricted signed sets on [n] is an intersecting antiehain if for any （A, f）, （B, g） ∈ A, they are incomparable and there exists x ∈ A ∩ B such that f（x） = g（x）. In this paper, we first give a LYM-type inequality for any intersecting antichain A of restricted signed sets, from which we then obtain ｜A｜≤ （r-1^n-1）（n-1）^r-1 if A. consists of restricted signed r-sets on [n]. Unless r = n = 3, equality holds if and only if A consists of all restricted signed r-sets （A, f） such that x0∈ A and f（x0） =ε0 for some fixed x0 ∈ [n], ε0 ∈ [n] ／ {x0}.     

Signed Total Domination Nnumber of a Graph

The signed total domination number of a graph is a certain variant of the domination number. If is a vertex of a graph G, then N() is its oper neighbourhood, i.e. the set of all vertices adjacent to in G. A mapping f: V(G)-1, 1, where V(G) is the vertex set of G, is called a signed total dominating function (STDF) on G, if for each V(G). The minimum of values , taken over all STDF's of G, is called the signed total domination number of G and denoted by _st(G). A theorem stating lower bounds for _st(G) is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on n-side prisms. At the end it is proved that _st(G) is not bounded from below in general.     

On Group Chromatic Number of Graphs

Let G be a graph and A an Abelian group. Denote by F(G, A) the set of all functions from E(G) to A. Denote by D an orientation of E(G). For f ∈ F(G,A), an (A,f)-coloring of G under the orientation D is a function c : V(G)↦A such that for every directed edge uv from u to v, c(u)−c(v) ≠ f(uv). G is A-colorable under the orientation D if for any function f ∈ F(G, A), G has an (A, f)-coloring. It is known that A-colorability is independent of the choice of the orientation. The group chromatic number of a graph G is defined to be the least positive integer m for which G is A-colorable for any Abelian group A of order ≥m, and is denoted by χ_g(G). In this note we will prove the following results. (1) Let H₁ and H₂ be two subgraphs of G such that V(H₁)∩V(H₂)=∅ and V(H₁)∪V(H₂)=V(G). Then χ_g(G)≤min{max{χ_g(H₁), max_v∈V(H2)deg(v,G)+1},max{χ_g(H₂), max_u∈V(H1) deg (u, G) + 1}}. We also show that this bound is best possible. (2) If G is a simple graph without a K_3,3-minor, then χ_g(G)≤5.     

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.     

Factors and Connected Induced Subgraphs

 Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg _G (x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑ _{x ∈ V ( G )} f(x) is odd. Received: June 29, 1998?Final version received: July 30, 1999     

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.     

Equitable total coloring of <Emphasis Type="Italic">F</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> ⋁ <Emphasis Type="Italic">W</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The minimum number of total independent partition sets of V ∪ E of graph G(V,E) is called the total chromatic number of G denoted by χ _t (G). If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χ _et (G). In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order. Supported by the National Natural Science Foundation of China (No. 10771091).     

A Generalization of Orthogonal Factorizations in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d _H (x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let = {F ₁, F ₂, ..., F _m } be a factorization of G and H be a subgraph of G with mr edges. If F _i , 1 ≤i≤m, has exactly r edges in common with H, then is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges. This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China     

Inequalities involving independence domination, f-domination, connected and total f-domination numbers

Let f be an integer-valued function defined on the vertex set V(G) of a graph G. A subset D of V(G) is an f-dominating set if each vertex x outside D is adjacent to at least f(x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by _f (G). In a similar way one can define the connected and total f-domination numbers _c,f (G) and _t,f (G). If f(x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving _f (G), _c,f (G), _t,f (G) and the independence domination number i(G). In particular, several known results are generalized.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{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 w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.