首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of VS is adjacent to a vertex in VS. The total restrained domination number of G, denoted by γ tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ tr (G)=n. Also, we show that γ tr (G)≤nΔ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δn−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.  相似文献   

2.
In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ t (G)Γ t (H)≤2Γ t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.  相似文献   

3.
Let G=(V,E) be a graph without isolated vertices. A set SV is a paired-dominating set if every vertex in VS is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math. 155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs.  相似文献   

4.
Let G=(V,E) be a graph. A set SV is a restrained dominating set if every vertex in VS is adjacent to a vertex in S and to a vertex in VS. The restrained domination number of G, denoted γ r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then gr(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then gr(G) £ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ r (G)=γ(G).  相似文献   

5.
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.  相似文献   

6.
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.  相似文献   

7.
For a permutation f of the vertex set V(G) of a connected graph G, let δ f (x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ f (G) of G with respect to f to be the sum of δ f (x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ f (G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.  相似文献   

8.
A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ pr(G), is the minimum cardinality of a paired-dominating set in G. A subset S?V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ ×2(G). A claw-free graph is a graph that does not contain K 1,3 as an induced subgraph. Chellali and Haynes (Util. Math. 67:161–171, 2005) showed that for every claw-free graph G, we have γ pr(G)≤γ ×2(G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K 1,r as an induced subgraph, then $\gamma_{\mathrm{pr}}(G)\le ( \frac{2r^{2}-6r+6}{r(r-1)} )\gamma_{\times2}(G)$ .  相似文献   

9.
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. We characterize the set of vertices of a tree that are contained in all, or in no, minimum paired-dominating sets of the tree. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.  相似文献   

10.
In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩SN[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating set.  相似文献   

11.
A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired dominating set of?G. A?graph with no isolated vertex is called paired domination vertex critical, or briefly γ pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ pr (G?v)<γ pr (G). A?γ pr -critical graph G is said to be k-γ pr -critical if γ pr (G)=k. In this paper, we firstly show that every 4-γ pr -critical graph of even order has a perfect matching if it is K 1,5-free and every 4-γ pr -critical graph of odd order is factor-critical if it is K 1,5-free. Secondly, we show that every 6-γ pr -critical graph of even order has a perfect matching if it is K 1,4-free.  相似文献   

12.
In a graph G, a vertex dominates itself and its neighbors. A subset SeqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of GS at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r k (G m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.  相似文献   

13.
Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C k (u,v). A k-container is a k *-container if it spans all vertices of G. We define G to be a k *-laceable graph if there is a k *-container joining any two vertices from different partite sets. A k *-container C k *(u,v)={P 1,…,P k } is equitable if ||V(P i )|−|V(P j )||≤2 for all 1≤i,jk. A graph is equitably k *-laceable if there is an equitable k *-container joining any two vertices in different partite sets. Let Q n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q n is equitably k *-laceable for all kn−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.  相似文献   

14.
A set S of vertices of a graph G=(V,E) without 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 number sdgt(G)\mathrm {sd}_{\gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sdgt(G) £ gt(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1 for some classes of graphs.  相似文献   

15.
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. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.  相似文献   

16.
This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset XV and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log 2 e(G)⌉≤t(G)≤⌈log 2 e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤24 or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤25 or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.  相似文献   

17.
On backbone coloring of graphs   总被引:1,自引:0,他引:1  
Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uvE(H) and |f(u)−f(v)|≥1 if uvE(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=TC with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.  相似文献   

18.
A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ toc (G) is the minimum size of such a set. We give some properties and bounds for γ toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.  相似文献   

19.
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 minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ p k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.  相似文献   

20.
A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity λ c (G) is the cardinality of a minimum cyclic edge-cut of G. We call a graph super cyclically edge-connected, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In this paper, we show that a connected vertex-transitive or edge-transitive graph is super cyclically edge-connected if either G is cubic with girth g(G)≥7, or G has minimum degree δ(G)≥4 and girth g(G)≥6.  相似文献   

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

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