首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
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).  相似文献   

2.
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 maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γpr(G)≤4n/5 if δ=1 and n≥3, Γpr(G)≤3n/4 if δ=2 and n≥6, and Γpr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γpr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γpr(G)=3n/4 are characterized.  相似文献   

3.
Let G=(V,E) be a graph. A set of vertices S?V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of $V-\nobreak S$ is adjacent to a vertex in V?S. The total restrained domination number of G, denoted by γ tr (G), is the smallest cardinality of a total restrained dominating set of G. A support vertex of a graph is a vertex of degree at least two which is adjacent to a leaf. We show that $\gamma_{\mathit{tr}}(T)\leq\lfloor\frac{n+2s+\ell-1}{2}\rfloor$ where T is a tree of order n≥3, and s and ? are, respectively, the number of support vertices and leaves of T. We also constructively characterize the trees attaining the aforementioned bound.  相似文献   

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

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

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

7.
We prove that the edges of every even graph G=G 1+G 2 that is the join of two regular graphs G i =(V i ,E i ) can be coloured with Δ(G) colours, whenever Δ(G)=Δ(G 2)+|V 1|. The proof of this result yields a combinatorial algorithm to optimally colour the edges of this type of graphs.  相似文献   

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

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

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

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

12.
Given a graph G=(V,E) with node weight w:VR + and a subset SV, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NPDTIME(n O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.  相似文献   

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

14.
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset SV of minimal size such that every vertex in VS is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.  相似文献   

15.
Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,yS,xy}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,yS,d(x,y)∈D}. The current paper studies distance graphs on the n-space R 1 n with 1-norm. In particular, most attention is paid to the subset Z 1 n of all lattice points of R 1 n . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.  相似文献   

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

17.
An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ a (G). Let mad(G)\mathop{\mathrm{mad}}(G) and Δ denote the maximum average degree and the maximum degree of a graph G, respectively.  相似文献   

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

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

20.
An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge eE such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S v (G,c) the set of colors assigned to the edges incident to a vertex vV, and D v (G,c) the minimum number of integers which must be added to S v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ vV D v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.  相似文献   

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

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