首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+βv(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and βv(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.  相似文献   

3.
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.  相似文献   

4.
We study the concept of strong equality of domination parameters. Let P1 and P2 be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P2 also has property P1. Let ψ1(G) and ψ2(G), respectively, denote the minimum cardinalities of sets with properties P1 and P2, respectively. Then ψ1(G2(G). If ψ1(G)=ψ2(G) and every ψ1(G)-set is also a ψ2(G)-set, then we say ψ1(G) strongly equals ψ2(G), written ψ1(G)≡ψ2(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γt(T), where γt(T) denotes the total domination number of T, is also presented.  相似文献   

5.
A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, and a double dominating set is a dominating set that dominates every vertex of G at least twice. We show that for trees, the paired-domination number is less than or equal to the double domination number, solving a conjecture of Chellali and Haynes. Then we characterize the trees having equal paired and double domination numbers.  相似文献   

6.
《Discrete Mathematics》2019,342(4):1213-1222
Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed.  相似文献   

7.
A broadcast on a graph G is a function f:VZ+∪{0}. The broadcast number of G is the minimum value of ∑vVf(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.  相似文献   

8.
9.
Let G=(V,E) be a simple graph. A subset SV is a dominating set of G, if for any vertex uV-S, there exists a vertex vS such that uvE. 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)=∑vVf(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].  相似文献   

10.
11.
12.
For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.  相似文献   

13.
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={vV(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if xV0 implies |N(x)∩V2|≤1 and xV1V2 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.  相似文献   

14.
A subset SS of vertices in a graph G=(V,E)G=(V,E) is a connected dominating set of GG if every vertex of V?SV?S is adjacent to a vertex in SS and the subgraph induced by SS is connected. The minimum cardinality of a connected dominating set of GG is the connected domination number γc(G)γc(G). The girth g(G)g(G) is the length of a shortest cycle in GG. We show that if GG is a connected graph that contains at least one cycle, then γc(G)≥g(G)−2γc(G)g(G)2, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.  相似文献   

15.
For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γks(G), is the minimum of ∑vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γks(G), the signed domination number γs(G) and the majority domination number γmaj(G).  相似文献   

16.
A graph G is dot-critical if contracting any edge decreases the domination number. Nader Jafari Rad (2009) [3] posed the problem: Is it true that a connected k-dot-critical graph G with G=0? is 2-connected? In this note, we give a family of 1-connected 2k-dot-critical graph with G=0? and show that this problem has a negative answer.  相似文献   

17.
A dominating set of a graph G=(V,E) is a subset SV such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γg(G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement . Graphs for which γg(Ge)>γg(G) for all edges eE are characterized, as are graphs for which γg(Ge)<γg(G) for all edges eE whenever is disconnected. Progress is reported in the latter case when is connected.  相似文献   

18.
Liying Kang 《Discrete Mathematics》2006,306(15):1771-1775
A function f defined on the vertices of a graph G=(V,E),f:V→{-1,0,1} is a total minus dominating function (TMDF) if the sum of its values over any open neighborhood is at least one. The weight of a TMDF is the sum of its function values over all vertices. The total minus domination number, denoted by , of G is the minimum weight of a TMDF on G. In this paper, a sharp lower bound on of k-partite graphs is given.  相似文献   

19.
We determine upper bounds on the ratios of several domination parameters in trees.  相似文献   

20.
In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γk(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γk(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号