In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and ...In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.展开更多
In this paper, we introduce the concepts of redundant constraint and exceptional vertex which play an important role in the characterization of universal minimal total dominating functions (universal MTDFs), and estab...In this paper, we introduce the concepts of redundant constraint and exceptional vertex which play an important role in the characterization of universal minimal total dominating functions (universal MTDFs), and establish some further results on universal MTDFs in general graphs. By extending these results to trees, we get a necessary and sufficient condition for universal MTDFs and show that there is a good algorithm for deciding whether a given tree has a universal MTDF.展开更多
Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such ...Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such that f(N(v)) ≥1 for every vertex v∈V . The signed total domination number of a graph G equals the minimum weight of a signed total dominating function on G . In this paper, some properties of the signed total domination number of a graph G are discussed.展开更多
Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on ...Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs.展开更多
Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination ...Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.展开更多
Let G be a finite connected simple graph with a vertex set V (G) and an edge set E(G). A total signed domination function of G is a function f : V (G) ∪ E(G) → {?1, 1}. The weight of f is w(f) = Σ x∈V(G)∪E(G) f(x...Let G be a finite connected simple graph with a vertex set V (G) and an edge set E(G). A total signed domination function of G is a function f : V (G) ∪ E(G) → {?1, 1}. The weight of f is w(f) = Σ x∈V(G)∪E(G) f(x). For an element x ∈ V (G) ∪ E(G), we define $f[x] = \sum\nolimits_{y \in N_T [x]} {f(y)} $ . A total signed domination function of G is a function f : V (G) ∪ E(G) → {?1, 1} such that f[x] ? 1 for all x ∈ V (G) ∪ E(G). The total signed domination number γ s * (G) of G is the minimum weight of a total signed domination function on G.In this paper, we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values of γ s * (G) when G is C n and P n .展开更多
基金This research is supported by the National Natural Science Foundation of China (No. 10371114).
文摘In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.
文摘In this paper, we introduce the concepts of redundant constraint and exceptional vertex which play an important role in the characterization of universal minimal total dominating functions (universal MTDFs), and establish some further results on universal MTDFs in general graphs. By extending these results to trees, we get a necessary and sufficient condition for universal MTDFs and show that there is a good algorithm for deciding whether a given tree has a universal MTDF.
文摘Let G=(V,E) be a simple graph. For any real valued function f:V →R, the weight of f is f(V) = ∑f(v) over all vertices v∈V . A signed total dominating function is a function f:V→{-1,1} such that f(N(v)) ≥1 for every vertex v∈V . The signed total domination number of a graph G equals the minimum weight of a signed total dominating function on G . In this paper, some properties of the signed total domination number of a graph G are discussed.
基金Project supported by the National Natural Science Foundation of China （Grant No.1057117）, and the Science Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）.
文摘Let G = （V, E） be a graph, and let f ： V →{-1, 1} be a two-valued function. If ∑x∈N（v） f（x） ≥ 1 for each v ∈ V, where N（v） is the open neighborhood of v, then f is a signed total dominating function on G. A set {fl, f2,… fd} of signed d total dominating functions on G with the property that ∑i=1^d fi（x） ≤ 1 for each x ∈ V, is called a signed total dominating family （of functions） on G. The maximum number of functions in a signed total dominating family on G is the signed total domatic number on G, denoted by dt^s（G）. The properties of the signed total domatic number dt^s（G） are studied in this paper. In particular, we give the sharp bounds of the signed total domatic number of regular graphs, complete bipartite graphs and complete graphs.
基金Supported by the National Natural Science Foundation of China (Grant No. 11061014)
文摘Let G = （V,E） be a graph.A function f ： E → {-1,1} is said to be a signed edge total dominating function （SETDF） of G if e ∈N（e） f（e ） ≥ 1 holds for every edge e ∈ E（G）.The signed edge total domination number γ st （G） of G is defined as γ st （G） = min{ e∈E（G） f（e）｜f is an SETDF of G}.In this paper we obtain some new lower bounds of γ st （G）.
基金the National Natural Science Foundation of China(Grant No.10471311)
文摘Let G be a finite connected simple graph with a vertex set V (G) and an edge set E(G). A total signed domination function of G is a function f : V (G) ∪ E(G) → {?1, 1}. The weight of f is w(f) = Σ x∈V(G)∪E(G) f(x). For an element x ∈ V (G) ∪ E(G), we define $f[x] = \sum\nolimits_{y \in N_T [x]} {f(y)} $ . A total signed domination function of G is a function f : V (G) ∪ E(G) → {?1, 1} such that f[x] ? 1 for all x ∈ V (G) ∪ E(G). The total signed domination number γ s * (G) of G is the minimum weight of a total signed domination function on G.In this paper, we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values of γ s * (G) when G is C n and P n .
