共查询到20条相似文献,搜索用时 15 毫秒
1.
It is shown that any k‐critical graph with n vertices contains a cycle of length at least , improving a previous estimate of Kelly and Kelly obtained in 1954. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 193–196, 2000 相似文献
2.
In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:131‐143, 2011 相似文献
3.
4.
5.
Benjamin R. Smith 《组合设计杂志》2010,18(6):401-414
In this article, we introduce a new technique for obtaining cycle decompositions of complete equipartite graphs from cycle decompositions of related multigraphs. We use this technique to prove that if n, m and λ are positive integers with n ≥ 3, λ≥ 3 and n and λ both odd, then the complete equipartite graph having n parts of size m admits a decomposition into cycles of length λ2 whenever nm ≥ λ2 and λ divides m. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph into cycles of length p2, where p is prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:401‐414, 2010 相似文献
6.
《Journal of Graph Theory》2018,87(1):46-60
Let be the largest integer such that, for all graphs G on n vertices, the edge set can be partitioned into at most parts, of which every part either is a single edge or forms a graph isomorphic to H. Pikhurko and Sousa conjectured that for and all sufficiently large n, where denotes the maximum number of edges of graphs on n vertices that do not contain H as a subgraph. A ‐fan is a graph on vertices consisting of k cliques of order r that intersect in exactly one common vertex. In this article, we verify Pikhurko and Sousa's conjecture for ‐fans. The result also generalizes a result of Liu and Sousa. 相似文献
7.
We prove that every bipartite C2l‐free graph G contains a C4‐free subgraph H with e(H) ≥ e(G)/(l – 1). The factor 1/(l – 1) is best possible. This implies that ex(n, C2l) ≤ 2(l – 1)ex(n, {C4, C2l}), which settles a special case of a conjecture of Erd?s and Simonovits. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 147–156, 2005 相似文献
8.
Petra Johann 《Journal of Graph Theory》2000,35(4):227-243
In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000 相似文献
9.
Let be a cycle of order 4. Write for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has vertices that have no subgraph isomorphic to . In this paper, we show that , where and is a prime number. Note that from Tait and Timmons's works. Since for every integer , one can find a prime such that , we obtain that . 相似文献
10.
设Kv是一个v点完全图.G是一个有限简单图.Kv上的一个图设计G-GD是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C^(r)2k,即带有一条弦的2k长圈,其中r表示弦的两个端点之间的顶点个数,1≤r≤k-1.文中给出了一个构作C^(r)m设计的统一方法,并得到关于v≡0,1(mod2k+1)时C^(r)2k-GD(v)的一系列结果. 相似文献
11.
The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999 相似文献
12.
Michael Tait 《Discrete Mathematics》2018,341(1):104-108
Let denote that any -coloring of contains a monochromatic . The degree Ramsey number of a graph , denoted by , is . We consider degree Ramsey numbers where is a fixed even cycle. Kinnersley, Milans, and West showed that , and Kang and Perarnau showed that . Our main result is that and . Additionally, we substantially improve the lower bound for for general . 相似文献
13.
14.
Lü Changhong 《高校应用数学学报(英文版)》2007,22(1):1-6
A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L : V(G) → {1,2 ,n}, where n = |V(G)|. An increasing nonconsecutive path in a labeled graph (G,L) is either a path (u1,u2 uk) (k ≥ 2) in G such that L(u,) + 2 ≤ L(ui+1) for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). A labeling L is optimal if the labeling L produces the largest d(G, L). In this paper, a method simpler than that in Zverovich (2004) to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained. 相似文献
15.
《Discrete Mathematics》2022,345(10):113012
An even cycle decomposition of a graph is a partition of its edges into even cycles. Markström constructed infinitely many 2-connected 4-regular graphs without even cycle decompositions. Má?ajová and Mazák then constructed an infinite family of 3-connected 4-regular graphs without even cycle decompositions. In this note, we further show that there exists an infinite family of 4-connected 4-regular graphs without even cycle decompositions. 相似文献
16.
17.
Barnaby Roberts 《Journal of Graph Theory》2017,85(2):429-445
We look at several saturation problems in complete balanced blow‐ups of graphs. We let denote the blow‐up of H onto parts of size n and refer to a copy of H in as partite if it has one vertex in each part of . We then ask how few edges a subgraph G of can have such that G has no partite copy of H but such that the addition of any new edge from creates a partite H. When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in 5 . Our main result is to calculate this value for when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n. We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from creates an extra partite copy of H. This problem turns out to be much simpler and we attain exact answers for all cliques and trees. 相似文献
18.
19.
Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G/E(C) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G, simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003 相似文献
20.
Richard Montgomery 《Random Structures and Algorithms》2019,54(4):779-796
For each , we show that any graph G with minimum degree at least has a fractional Kr‐decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional Kr‐decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery, and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery, and Osthus, this shows that, for any graph F with chromatic number , and any , any sufficiently large graph G with minimum degree at least has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition. 相似文献