首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
A graph G is domination perfect if for each induced subgraph H of G, γ(H) = i(H), where γ and i are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of domination perfect graphs. This characterization is not correct, but the ideas in [3] can be used to weaken the known sufficient conditions for a graph to be domination perfect and to obtain short proofs of some results regarding domination perfect graphs. © 1993 John Wiley & Sons, Inc.  相似文献   

2.
3.
A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.  相似文献   

4.
Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.  相似文献   

5.
In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Qn has an independent perfect domination set if and only if Qn is a regular covering of the complete graph Kn+1 if and only if n = 2m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001  相似文献   

6.
Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is calledΓ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) = IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.  相似文献   

7.
8.
Let G be a graph of order n and maximum degree Δ(G) and let γt(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the 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 Gv is less than the total domination number of G. We call these graphs γt-critical. For any γt-critical graph G, it can be shown that nΔ(G)(γt(G)−1)+1. In this paper, we prove that: Let G be a connected γt-critical graph of order n (n≥3), then n=Δ(G)(γt(G)−1)+1 if and only if G is regular and, for each vV(G), there is an AV(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.  相似文献   

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

10.
An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.  相似文献   

11.
A graph G is 2-stratified if its vertex set is partitioned into two nonempty 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 for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.  相似文献   

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

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

15.
A secure dominating set X of a graph G is a dominating set with the property that each vertex uVGX is adjacent to a vertex vX 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(Ge)>γs(G) for any edge e of G, bipartite γs-ER-critical graphs and γs-ER-critical trees.  相似文献   

16.
17.
18.
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.  相似文献   

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

20.
Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.  相似文献   

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

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