共查询到20条相似文献,搜索用时 46 毫秒
1.
《Quaestiones Mathematicae》2013,36(6):749-757
AbstractA 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. 相似文献
2.
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 相似文献
3.
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. 相似文献
4.
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 sdgR(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. 相似文献
5.
《Quaestiones Mathematicae》2013,36(5):613-629
AbstractLet R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by ΓI (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this paper is to study the dominating sets and domination number of ΓI (R) and the comaximal graph CG2(R) \ J (R) (or CGJ (R) for short) where CG2(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R. 相似文献
6.
A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γd(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γd(G)≤α(1+2ln(n/α)). 相似文献
7.
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]. 相似文献
8.
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. 相似文献
9.
Richard C. Brewster Christina M. Mynhardt Laura E. Teshima 《Central European Journal of Mathematics》2013,11(7):1334-1343
A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ v∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λb(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λb. 相似文献
10.
Huajun Tang 《Discrete Mathematics》2008,308(15):3416-3419
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. 相似文献
11.
A set of vertices S is said to dominate the graph G if for each v ? S, there is a vertex u ∈ S with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, u ∈ V(G) with v not adjacent to u, γ(G + vu) < γ(G). Thus G is k-y-critical if γ(G) = k and for each edge e ? E(G), γ(G + e) = k ?1. The 2-domination critical graphs are characterized the properties of the k-critical graphs with k ≥ 3 are studied. In particular, the connected 3-critical graphs of even order are shown to have a 1-factor and some stringent restrictions on their degree sequences and diameters are obtained. 相似文献
12.
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 (V0,V1,V2) of V(G), where Vi={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V0 implies |N(x)∩V2|≤1 and x∈V1∪V2 implies that |N(x)∩V2|=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 uR(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. 相似文献
13.
14.
P.J.P. Grobler 《Discrete Mathematics》2009,309(19):5820-496
A secure dominating set X of a graph G is a dominating set with the property that each vertex u∈VG−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. 相似文献
15.
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. 相似文献
16.
A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs. 相似文献
17.
A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt(G) of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, 1?sdγt(T)?3. In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3. 相似文献
18.
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. 相似文献
19.
A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of v∈V(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture. 相似文献
20.
Sambhu Charan Barman Sukumar Mondal Madhumangal Pal 《Journal of Applied Mathematics and Computing》2013,43(1-2):133-150
For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ ×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D 2 is said to be minimal if there does not exist any D′?D 2 such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D 2, denoted by γ ×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n 2) time. 相似文献