共查询到20条相似文献,搜索用时 234 毫秒
1.
Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14. 相似文献
2.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Received: August 19, 1998 Final version received: May 17, 2000 相似文献
3.
Zhi-quanHu FengTian 《应用数学学报(英文版)》2003,19(1):97-106
A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G)≥3κ-1/2 or δ(G)≥5κ-4.Several known results are generalized. 相似文献
4.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
5.
Kazuhide Hirohata 《Graphs and Combinatorics》2000,16(3):269-273
Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d
G(u), d
G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d
G(u,v)=2. Then x and y are connected by a path of length at least d−|W|.
Received: February 5, 1998 Revised: April 13, 1998 相似文献
6.
A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n +IV21)/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3. 相似文献
7.
Closed Separator Sets 总被引:1,自引:0,他引:1
Matthias Kriesell 《Combinatorica》2005,25(5):575-598
A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G.
A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G.
A graph H with
is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán.
Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree. 相似文献
8.
Let G=(I
n
,E) be the graph of the n-dimensional cube. Namely, I
n
={0,1}
n
and [x,y]∈E whenever ||x−y||1=1. For A⊆I
n
and x∈A define h
A
(x) =#{y∈I
n
A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I
n
of size 2
n−1
we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices.
Received: January 7, 2000
RID="*"
ID="*" Supported in part by BSF and by the Israeli academy of sciences 相似文献
9.
(3,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7.
Revised: September 21, 1998 相似文献
10.
Let G = (V, E) be a graph. A set S í V{S \subseteq 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. The total restrained domination number of G, denoted by γ
tr
(G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ
tr
(G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ
tr
(G) ≤ n − diam(G) − r + 1. 相似文献
11.
Pravin M. Vaidya 《Discrete and Computational Geometry》1991,6(1):369-381
A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and
the weight of an edge between any two points is the distance between the points under someL
p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε
−k
log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε−k
n). 相似文献
12.
Marcin KRZYWKOWSKI 《数学年刊B辑(英文版)》2012,33(1):113-126
A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one. 相似文献
13.
Total Domination in Graphs with Given Girth 总被引:1,自引:0,他引:1
A set S of vertices in a graph G without isolated vertices is a total dominating set of G 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 γ
t
(G) of G. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in
terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g, then γ
t
(G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs.
Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. 相似文献
14.
. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG
* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G
* is equal to G
2.
If G is k-connected, we cover the vertices of G by at most ⌈α(G
*)/k⌉ cycles, where α(G
*) is the stability number of the partially square graph of G. On the other hand we consider in G
* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑
x
∈
S
deg
G
(x)≥|G|, for every t-stable set S⊆V(G) of G
* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given.
Received: January 22, 1997 Final version received: February 15, 2000 相似文献
15.
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. 相似文献
16.
Peter Dankelmann Johannes H. Hattingh Michael A. Henning Henda C. Swart 《Journal of Global Optimization》2006,34(4):597-607
Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γr(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence
of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γr(T); (ii) T is a γ-excellent tree and T ≠ K2; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γr(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality. 相似文献
17.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
18.
On Hamiltonian Powers of Digraphs 总被引:2,自引:0,他引:2
Antoni Marczyk 《Graphs and Combinatorics》2000,16(1):103-113
For a strongly connected digraph D, the k-th power D
k of D is the digraph with the same set of vertices, a vertex x being joined to a vertex y in D
k if the directed distance from x to y in D is less than or equal to k. It follows from a result of Ghouila-Houri that for every digraph D on n vertices and for every k≥n/2, D
k is hamiltonian. In the paper we characterize these digraphs D of odd order whose (⌈n/2 ⌉−1)-th power is hamiltonian.
Revised: June 13, 1997 相似文献
19.
Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform
coverage radius in O(n
2) time, when G is an interval graph containing n vertices. 相似文献
20.
A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ
tc
(G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ
tc
(G) + γ
tc
($
\bar G
$
\bar G
), and characterize the extremal graphs achieving these bounds. 相似文献