共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
V. E. Zverovich 《Journal of Graph Theory》1998,29(3):139-149
Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998 相似文献
4.
Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002 相似文献
5.
6.
A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. A set of vertices U in a graph G is irredundant if each vertex v of U has a private neighbor, which may be v itself, i.e., a neighbor of v which is not a neighbor of any other vertex of U. The independence number α (resp. upper irredundance number IR) is the maximum number of vertices of an independent (resp. irredundant) set of G. In previous work, a series of best possible lower and upper bounds on α and some other usual invariants of G were obtained by the system AGX 2, and proved either automatically or by hand. These results are strengthened in the present paper by systematically replacing α by IR. The resulting conjectures were tested by AGX which could find no counter-example to an upper bound nor any case where a lower bound could not be shown to remain tight. Some proofs for the bounds on α carry over. In all other cases, new proofs are provided. 相似文献
7.
E.J. Cockayne 《Discrete Mathematics》2008,308(23):5358-5375
A necessary and sufficient condition for an open irredundant set of vertices of a graph to be maximal is obtained. This result is used to show that the smallest cardinality amongst the maximal open irredundant sets in an n-vertex isolate-free graph with maximum degree Δ is at least n(3Δ−1)/(2Δ3−5Δ2+8Δ−1) for Δ≥5, n/8 for Δ=4 and 2n/11 for Δ=3. The bounds are the best possible. 相似文献
8.
Kung-Jui Pai 《Discrete Applied Mathematics》2010,158(10):1079-1089
The power domination problem is to find a minimum placement of phase measurement units (PMUs) for observing the whole electric power system, which is closely related to the classical domination problem in graphs. For a graph G=(V,E), the power domination number of G is the minimum cardinality of a set S⊆V such that PMUs placed on every vertex of S results in all of V being observed. A vertex with a PMU observes itself and all its neighbors, and if an observed vertex with degree d>1 has only one unobserved neighbor, then the unobserved neighbor becomes observed. Although the power domination problem has been proved to be NP-complete even when restricted to some special classes of graphs, Dorfling and Henning in [M. Dorfling, M.A. Henning, A note on power domination in grid graphs, Discrete Applied Mathematics 154 (2006) 1023-1027] showed that it is easy to determine the power domination number of an n×m grid. Their proof provides an algorithm for giving a minimum placement of PMUs. In this paper, we consider the situation in which PMUs may only be placed within a restricted subset of V. Then, we present algorithms to solve this restricted type of power domination on grids under the conditions that consecutive rows or columns form a forbidden zone. Moreover, we also deal with the fault-tolerant measurement placement in the designed scheme and provide approximation algorithms when the number of faulty PMUs does not exceed 3. 相似文献
9.
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, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n. 相似文献
10.
11.
12.
13.
Stephanie A. RickettTeresa W. Haynes 《Discrete Applied Mathematics》2011,159(10):1053-1057
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. 相似文献
14.
Odile Favaron 《Journal of Graph Theory》1986,10(4):429-438
In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V – X is joined to at least one vertex of X. A set X is called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that is a vertex of V – X joined to it but to no other vertex of X. Let α′ and α, γ, and Γ, ir and IR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known that ir ? γ ? α′ ? α ? Γ ? IR and that if G does not contain any induced subgraph isomorphic to K1,3, then γ = α′. Here we prove that if G contains no induced subgraph isomorphic to K1,3 or to the graph H of figure 1, then ir = γ = α′. We prove also that if G contains no induced subgraph isomorphic to K1,3, to H, or to the graph h of figure 3, then Γ = IR. Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for γ = ir in terms of forbidden subgraphs. 相似文献
15.
16.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2005,55(2):393-396
The restrained domination number r(G) and the total restrained domination number
t
r
(G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic. 相似文献
17.
18.
19.
20.
O. Favaron H. Karami R. Khoeilar S. M. Sheikholeslami L. Volkmann 《Journal of Graph Theory》2010,64(4):323-329
Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b‐dimensional cube is a Cartesian product I1×I2×···×Ib, where each Ii is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ?log2ψ(G)?. In this article, we show that for an interval graph G ?log2ψ(G)??cub(G)??log2ψ(G)?+2. It is not clear whether the upper bound of ?log2ψ(G)?+2 is tight: till now we are unable to find any interval graph with cub(G)>?log2ψ(G)?. We also show that for an interval graph G, cub(G)??log2α?, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ?log2α2?. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I1×I2×···×Ib, where each Ii is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k‐dimensional boxes. It is clear that box(G)?cub(G). From the above result, it follows that for any graph G, cub(G)?box(G)?log2α?. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010 相似文献