共查询到20条相似文献,搜索用时 31 毫秒
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.
A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d
T
(x,y)−d
G
(x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G.
Received: July 3, 1998 Final version received: August 10, 1999 相似文献
3.
A set U of vertices of a graph G is called a geodetic set if the union of all the geodesics joining pairs of points of U is the whole graph G. One result in this paper is a tight lower bound on the minimum number of vertices in a geodetic set. In order to obtain
that result, the following extremal set problem is solved. Find the minimum cardinality of a collection 𝒮 of subsets of [n]={1,2,…,n} such that, for any two distinct elements x,y∈[n], there exists disjoint subsets A
x
,A
y
∈𝒮 such that x∈A
x
and y∈A
y
. This separating set problem can be generalized, and some bounds can be obtained from known results on families of hash functions.
Received: May 19, 2000 Final version received: July 5, 2001 相似文献
4.
. 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 相似文献
5.
Raffaele Mosca 《Graphs and Combinatorics》2001,17(3):517-528
Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ
n
:Ex≤1,x≥0}, P(C)={x∈ℜ
n
:Cx≤1,x≥0}, α
E
(G)=max{1
T
x subject to x∈P(E)}, and α
C
(G)= max{1
T
x subject to x∈P(C)}. In this paper we prove that if α
E
(G)=α
C
(G), then γ(G)=θ(G).
Received: May 20, 1998?Final version received: April 12, 1999 相似文献
6.
M. R. Darafsheh 《Acta Appl Math》2010,110(3):1225-1235
Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑{x,y}⊆V
d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑
e=uv∈E
n
u
(e|G)n
v
(e|G), where n
u
(e|G) (resp. n
v
(e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑
e=uv∈E
[n
eu
(e|G)+n
ev
(e|G)], where n
eu
(e|G) (resp. n
ev
(e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods. 相似文献
7.
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). 相似文献
8.
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. 相似文献
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.
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. 相似文献
11.
Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg
F
(x)≤f(x) for all x∈V(G) and deg
F
(y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property.
Received: June 14, 1999?Final version received: August 21, 2000 相似文献
12.
Convex Sets Under Some Graph Operations 总被引:1,自引:0,他引:1
Given a connected graph G, we say that a set C⊆V(G) is convex in G if, for every pair of vertices x,y∈C, the vertex set of every x-y geodesic in G is contained in C. The cardinality of a maximal proper convex set in G is the convexity number of G. In this paper, we characterize the convex sets of graphs resulting from some binary operations, and compute the convexity
numbers of the resulting graphs.
Received: October, 2001 Final version received: September 4, 2002
Acknowledgments. The authors would like to thank the referee for the helpful suggestions and useful comments. 相似文献
13.
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. 相似文献
14.
Chain graphs are exactly bipartite graphs without induced 2K
2 (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned
probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G
* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned
probe graphs, and gives an O(m
2)-time recognition algorithm for chain partitioned probe graphs. 相似文献
15.
For x and y vertices of a connected graph G, let TG(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which TG(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time TG(x, y) to reach y from x in this graph is approximately 4n3/27. 相似文献
16.
Let G = (V, E) be a graph and x, y, z ∈ V be three designated vertices. We give a necessary and sufficient condition for the existence of a rigid two-dimensional framework
(G, p), in which x, y, z are collinear. This result extends a classical result of Laman on the existence of a rigid framework on G. Our proof leads to an efficient algorithm which can test whether G satisfies the condition.
Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization, and the Hungarian Scientific Research Fund
grant no. F034930, T037547, and FKFP grant no. 0143/2001. 相似文献
17.
Let R be an arbitrary ring, S be a subset of R, and Z(S) = {s ∈ S | sx = xs for every x ∈ S}. The commuting graph of S, denoted by Γ(S), is the graph with vertex set S \ Z(S) such that two different vertices x and y are adjacent if and only if xy = yx. In this paper, let I
n
, N
n
be the sets of all idempotents, nilpotent elements in the quaternion algebra ℤ
n
[i, j, k], respectively. We completely determine Γ(I
n
) and Γ(N
n
). Moreover, it is proved that for n ≥ 2, Γ(I
n
) is connected if and only if n has at least two odd prime factors, while Γ(N
n
) is connected if and only if n ∈ 2, 22, p, 2p for all odd primes p. 相似文献
18.
Let G be a non-abelian group and associate a non-commuting graph ∇(G) with G as follows: the vertex set of ∇(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. In this short paper we prove that if G is a finite group with ∇(G) ≅ ∇(M), where M = L
2(q) (q = p
n
, p is a prime), then G ≅ M.
相似文献
19.
20.
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 相似文献