共查询到20条相似文献,搜索用时 31 毫秒
1.
For a setS of points in the plane, letd
1>d
2>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd
k
. It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk
2. IfS consists of the vertices of a convex polygon and |S|constk
2, then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon. 相似文献
2.
A connected graph G is called t-tough if t · w(G - S) ? |S| for any subset S of V(G) with w(G - S) > 1, where w(G - S) is the number of connected components of G - S. We prove that every k-tough graph has a k-factor if k|G| is even and |G| ? k + 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integer k and for any positive real number ε, there exists a (k - ε)-tough graph G with k|G| even and |G| ? k + 1 which has no k-factor. 相似文献
3.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
4.
Hao Li 《Graphs and Combinatorics》2000,16(3):319-335
Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C
′ with |C
′∩S|>|C∩S|. We also show that if ∑4
i=1
d(a
i)≥n+3+|⋂4
i=1
N(a
i)| for any four independent vertices a
1, a
2, a
3, a
4 in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S.
Received: March 9, 1998 Revised: January 7, 1999 相似文献
5.
One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S1 + deg S2 ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S1, S2 ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed. 相似文献
6.
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 相似文献
7.
Our topic is an extension of the following classical result of Hall to hypergraphs: A bipartite graph G contains a perfect matching if and only if for each independent set X of vertices, at least |X| vertices of G are adjacent to some vertex of X. Berge generalized the concept of bipartite graphs to hypergraphs by defining a hypergraph G to be balanced if each odd cycle in G has an edge containing at least three vertices of the cycle. Based on this concept, Conforti, Cornuéjols, Kapoor, and Vušković
extended Hall's result by proving that a balanced hypergraph G contains a perfect matching if and only if for any disjoint sets A and B of vertices with |A| > |B|, there is an edge in G containing more vertices in A than in B (for graphs, the latter condition is equivalent to the latter one in Hall's result). Their proof is non-combinatorial and
highly based on the theory of linear programming. In the present paper, we give an elementary combinatorial proof.
Received April 29, 1997 相似文献
8.
LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev.
This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars
(No. 10425103) and the Key Program of NSF (No. 10331020) in China. 相似文献
9.
H. J. Broersma J. Den Van Heuvel H. A. Jung H. J. Veldman 《Journal of Graph Theory》1993,17(3):373-385
For a graph G and an integer k, denote by Vk the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc. 相似文献
10.
Vsevolod F. Lev 《Combinatorica》2008,28(4):491-497
For any abelian group G and integer t ≥ 2 we determine precisely the smallest possible size of a non-t-rectifiable subset of G. Specifically, assuming that G is not torsion-free, denote by p the smallest order of a non-zero element of G. We show that if a subset S ⊆ G satisfies |S| ≤ ⌌log
t
p⌍, then S is t-isomorphic (in the sense of Freiman) to a set of integers; on the other hand, we present an example of a subset S ⊆ G with |S| = ⌌log
t
p⌍ + 1 which is not t-isomorphic to a set of integers. 相似文献
11.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
12.
A graph G is close to regular or more precisely a (d, d + k)-graph, if the degree of each vertex of G is between d and d + k. Let d ≥ 2 be an integer, and let G be a connected bipartite (d, d+k)-graph with partite sets X and Y such that |X|- |Y|+1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d +7 when k = 1,·n ≥ 4d+ 5 when k = 2,·n ≥ 4d+3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible. 相似文献
13.
A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ+(G) = max{d+(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)2 + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998 相似文献
14.
Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections Si = {v ? V(G)\S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with si = |Si|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem. 相似文献
15.
D.R Woodall 《Journal of Combinatorial Theory, Series B》1978,25(2):184-186
A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which for every non-empty subset S of the vertices of G, then G is Hamiltonian. 相似文献
16.
Michael B. Dillencourt 《Journal of Graph Theory》1994,18(1):103-107
The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph. 相似文献
17.
Pirzada S Zhou Guofei 《高校应用数学学报(英文版)》2007,22(4):485-489
Given non-negative integers m,n,h and k with m ≥ h > 1 and n ≥ k > 1, an (h, k)-bipartite hypertournament on m n vertices is a triple (U, V, A), where U and V are two sets of vertices with |U| = m and |V| = n, and A is a set of (h k)-tuples of vertices,called arcs, with at most h vertices from U and at most k vertices from V, such that for any h k subsets U1 ∪ V1 of U ∪ V, A contains exactly one of the (h k)! (h k)-tuples whose entries belong to U1 ∪ V1. Necessary and sufficient conditions for a pair of non-decreasing sequences of non-negative integers to be the losing score lists or score lists of some(h, k)-bipartite hypertournament are obtained. 相似文献
18.
Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph G≠K2 is 0‐antimagic. On the other hand, there are connected graphs G≠K2 which are not weighted‐1‐antimagic. It is unknown whether every connected graph G≠K2 is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph G≠K2 on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
19.
LetA={a
1, …,a
k} and {b
1, …,b
k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata
i+b
i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to
the groupsZ
p
r
andZ
p
rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that
Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|.
This work has been supported partly by NSFC grant number 19971058 and 10271080. 相似文献
20.
For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007 相似文献