共查询到20条相似文献,搜索用时 31 毫秒
1.
We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph Kn contains a k-connected monochromatic subgraph with at least n-2(k-1) vertices. This conjecture, if true, is best possible. Here we prove it for k=2, and show how to reduce it to the case n<7k-6. We prove the following result as well: for n>16k every 2-colored Kn contains a k-connected monochromatic subgraph with at least n-12k vertices. 相似文献
2.
Let Gn,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property Ak, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant Ck such that if 2m ≥ Ckn then Ak occurs in Gn,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000 相似文献
3.
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular
bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings Mk exist with |Mk∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k. 相似文献
4.
Sibel Ozkan 《Discrete Mathematics》2009,309(14):4883-1973
A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:
- 1.
- has a Hamilton decomposition, and
- 2.
- has a complement in Kn that is primitive.
5.
J. Harant M. Voigt S. Jendrol B. Randerath Z. Ryj
ek I. Schiermeyer 《Journal of Graph Theory》2001,36(3):131-143
Let G be a K1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001 相似文献
6.
We prove that for every fixed k and ? ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2 ?. This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which are Ramsey, that is, have the property that for every k, any k‐edge coloring of a sufficiently large Qn contains a monochromatic copy of H. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 196–208, 2006 相似文献
7.
Allan Lo 《Combinatorica》2016,36(4):471-492
Let K c n be an edge-coloured complete graph on n vertices. Let Δmon(Kc n) denote the largest number of edges of the same colour incident with a vertex of Kc n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and Erd?s[6] conjectured that every Kc n with Δmon(Kc n)<?n/2?contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n0 such that every Kc n with Δmon(Kc n)<(1/2–ε)n and n≥n0 contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and Erd?s is true asymptotically. 相似文献
8.
Izolda Gorgol 《Graphs and Combinatorics》2008,24(4):327-331
A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K
n
with no rainbow copy of H. The rainbow number
rb(n, H) is the minimum number of colors such that any edge-coloring of K
n
with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers.
We show that for n ≥ k + 1, where C
k
+ denotes a cycle C
k
with a pendant edge. 相似文献
9.
The complete tripartite graph K
n,n,n has 3n
2 edges. For any collection of positive integers x
1, x
2,...,x
m with
and x
i ⩾ 3 for 1 ⩽ i ⩽ m, we exhibit an edge-disjoint decomposition of K
n,n,n into closed trails (circuits) of lengths x
1, x
2,..., x
m.
Supported by Ministry of Education of the Czech Republic as project LN00A056. 相似文献
10.
11.
Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v1a1v2v3···vt−1vt of distinct vertices v1, v2,⋖, vt and distinct arcs a1, ⋖, at−1 such that vi precedes vt−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as vi's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997 相似文献
12.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n). 相似文献
13.
Hong Wang 《Journal of Graph Theory》1999,31(2):101-106
In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V1, V2, E) is a bipartite graph with |V1| = |V2| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V1, V2; E) is a bipartite graph such that |V1| = |V2| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U1, U2; F) with |U1| ≤ n, |U2| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999 相似文献
14.
Po‐Shen Loh 《Random Structures and Algorithms》2014,44(3):328-354
One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph Gn,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of Gn,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014 相似文献
15.
Let k be a fixed integer and fk(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists dk(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999 相似文献
16.
Andrzej Dudek Christian Reiher Andrzej Ruciski Mathias Schacht 《Random Structures and Algorithms》2020,56(1):122-141
We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one. 相似文献
17.
P. Valtr 《Discrete and Computational Geometry》1998,19(3):461-469
A geometric graph is a graph G=(V,E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight-line segments between points of V . Two edges of a geometric graph are said to be parallel if they are opposite sides of a convex quadrilateral.
In this paper we show that, for any fixed k ≥ 3 , any geometric graph on n vertices with no k pairwise parallel edges contains at most O(n) edges, and any geometric graph on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. We also prove a conjecture by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n-2 edges.
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p461.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 27, 1997, and in revised form March 4, 1997, and June 16, 1997. 相似文献
18.
In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Zk, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph. 相似文献
19.
Colour the edges of a complete graph withn vertices in such a way that no vertex is on more thank edges of the same colour. We prove that for everyk there is a constantc
ksuch that ifn>c
kthen there is a Hamiltonian cycle with adjacent edges having different colours. We prove a number of other results in the
same vein and mention some unsolved problems. 相似文献
20.
A 1-factor of a graph G = (V, E) is a collection of disjoint edges which contain all the vertices of V. Given a 2n - 1 edge coloring of K2n, n ≥ 3, we prove there exists a 1-factor of K2n whose edges have distinct colors. Such a 1-factor is called a “Rainbow.” © 1998 John Wiley & Sons, Inc. J Combin Designs 6:1–20, 1998 相似文献