共查询到20条相似文献,搜索用时 31 毫秒
1.
Ronald D. Dutton 《Discrete Mathematics》2009,309(13):4443-46
A secure set S⊆V of graph G=(V,E) is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of “attack” and “defended.” The set S is secure when |N[X]∩S|≥|N[X]−S| for every X⊆S. The smallest cardinality of a secure set in G is the security number of G. New bounds for the security number are established, the effect of some graph modifications on the security number is investigated, and the exact value of the security number for some families of graphs is given. 相似文献
2.
Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented. 相似文献
3.
Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. Necessary and sufficient conditions for a set to be secure are determined. 相似文献
4.
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. 相似文献
5.
Katarzyna Jesse-Józefczyk 《Central European Journal of Mathematics》2012,10(3):1113-1124
Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for
trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances. 相似文献
6.
Assume that each vertex of a graph G is the possible location for an “intruder” such as a thief, or a saboteur, a fire in a facility or some possible processor fault in a computer network. A device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v]and to identify at which vertex inN[v] the intruder is located. One must then have a dominating set S⊆V(G), a set with ∪v∈SN[v]=V(G), to be able to identify any intruder’s location. If any one device can fail to detect the intruder, then one needs a double-dominating set. This paper considers liar’s dominating sets, sets that can identify an intruder’s location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location. Liar’s dominating sets lie between double dominating sets and triple dominating sets because every triple dominating set is a liar’s dominating set, and every liar’s dominating set must double dominate. 相似文献
7.
Johannes H. Hattingh 《Discrete Applied Mathematics》2009,157(13):2846-2858
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γr(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then . 相似文献
8.
9.
Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γtr(G) (γr(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P3, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds. 相似文献
10.
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) 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 an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γt(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γr(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γt(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γt(G)=n-Δ. 相似文献
11.
Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted Ih[S], is the smallest convex set containing S. A set S is a hull set of G if Ih[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph. 相似文献
12.
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]. 相似文献
13.
Joanna Raczek 《Discrete Mathematics》2008,308(1):44-50
For a given connected graph G=(V,E), a set Dtr⊆V(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. 相似文献
14.
15.
Let H be some fixed graph of order p. For a given graph G and vertex set S⊆V(G), we say that S is H-decomposable if S can be partitioned as S=S1∪S2∪?∪Sj where, for each of the disjoint subsets Si, with 1?i?j, we have |Si|=p and H is a spanning subgraph of 〈Si〉, the subgraph induced by Si. We define the H-domination number of G, denoted as γH(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write γH(G)=∞. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for γH(G). We show, in particular, that if δ(G)?2, then γP3(G)?3γ(G). Also, if γP3(G)=3γ(G), then every γ(G)-set is an efficient dominating set. 相似文献
16.
Joanna Raczek 《Discrete Mathematics》2008,308(23):5570-5575
Let G=(V,E) be a graph with δ(G)≥1. A set D⊆V is a paired dominating set if D is dominating, and the induced subgraph 〈D〉 contains a perfect matching. The paired domination number of G, denoted by γp(G), is the minimum cardinality of a paired dominating set of G. The paired bondage number, denoted by bp(G), is the minimum cardinality among all sets of edges E′⊆E such that δ(G−E′)≥1 and γp(G−E′)>γp(G). We say that G is a γp-strongly stable graph if, for all E′⊆E, either γp(G−E′)=γp(G) or δ(G−E′)=0. We discuss the basic properties of paired bondage and give a constructive characterization of γp-strongly stable trees. 相似文献
17.
A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results. 相似文献
18.
Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6. 相似文献
19.
Tomoki Yamashita 《Discrete Mathematics》2008,308(24):6584-6587
Let G be a graph. For S⊂V(G), let Δk(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ2(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ2(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles. 相似文献
20.
Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture. 相似文献