首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
A graph G is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free.  相似文献   

2.
In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span Tμ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on Tμ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min–max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov–Frank theorem for directed free multiflows and Ibaraki–Karzanov–Nagamochi’s directed multiflow locking theorem as special cases.  相似文献   

3.
4.
We show that if X is a Banach space with a Schauder basis, ΩX is a pseudoconvex open subset, and u:Ω→(−∞,∞) is a locally bounded function, then there is a continuous plurisubharmonic function w:Ω→(−∞,∞) with u(x)?w(x) for all xΩ. This has many applications to analytic cohomology of complex Banach manifolds.  相似文献   

5.
Let X be a separable Banach space and u:XR locally upper bounded. We show that there are a Banach space Z and a holomorphic function h:XZ with u(x)<‖h(x)‖ for xX. As a consequence we find that the sheaf cohomology group Hq(X,O) vanishes if X has the bounded approximation property (i.e., X is a direct summand of a Banach space with a Schauder basis), O is the sheaf of germs of holomorphic functions on X, and q?1. As another consequence we prove that if f is a C1-smooth -closed (0,1)-form on the space X=L1[0,1] of summable functions, then there is a C1-smooth function u on X with on X.  相似文献   

6.
The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 1998, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γP(G) of a graph G is the minimum cardinality of a power dominating set of G. In this paper, we present upper bounds on the power domination number for a connected graph with at least three vertices and a connected claw-free cubic graph in terms of their order. The extremal graphs attaining the upper bounds are also characterized.  相似文献   

7.
A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersdγt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.  相似文献   

8.
Let G be a graph of order n, minimum degree δ?2, girth g?5 and domination number γ. In 1990 Brigham and Dutton [Bounds on the domination number of a graph, Q. J. Math., Oxf. II. Ser. 41 (1990) 269-275] proved that γ?⌈n/2-g/6⌉. This result was recently improved by Volkmann [Upper bounds on the domination number of a graph in terms of diameter and girth, J. Combin. Math. Combin. Comput. 52 (2005) 131-141; An upper bound for the domination number of a graph in terms of order and girth, J. Combin. Math. Combin. Comput. 54 (2005) 195-212] who for i∈{1,2} determined a finite set of graphs Gi such that γ?⌈n/2-g/6-(3i+3)/6⌉ unless G is a cycle or GGi.Our main result is that for every iN there is a finite set of graphs Gi such that γ?n/2-g/6-i unless G is a cycle or GGi. Furthermore, we conjecture another improvement of Brigham and Dutton's bound and prove a weakened version of this conjecture.  相似文献   

9.
For a given connected graph G=(V,E), a set DtrV(G) is a total restrained dominating set if it is dominating and both 〈Dtr〉 and 〈V(G)-Dtr〉 do not contain isolate vertices. The cardinality of the minimum total restrained dominating set in G is the total restrained domination number and is denoted by γtr(G). In this paper we characterize the trees with equal total and total restrained dominating numbers and give a lower bound on the total restrained dominating number of a tree T in terms of its order and the number of leaves of T.  相似文献   

10.
In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.  相似文献   

11.
《Quaestiones Mathematicae》2013,36(8):1101-1115
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.  相似文献   

12.
A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.  相似文献   

13.
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class.) We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. In this paper we investigate the F-domination number when (i) F is a 2-stratified path P3 on three vertices rooted at a blue vertex which is a vertex of degree 1 in the P3 and is adjacent to a blue vertex and with the remaining vertex colored red, and (ii) F is a 2-stratified K3 rooted at a blue vertex and with exactly one red vertex.  相似文献   

14.
A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.  相似文献   

15.
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.  相似文献   

16.
The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.  相似文献   

17.
A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.  相似文献   

18.
On the 2-rainbow domination in graphs   总被引:2,自引:0,他引:2  
The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism GK2. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.  相似文献   

19.
We provide a simple constructive characterization for trees with equal domination and independent domination numbers, and for trees with equal domination and total domination numbers. We also consider a general framework for constructive characterizations for other equality problems.  相似文献   

20.
A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γt-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).  相似文献   

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

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