共查询到20条相似文献,搜索用时 15 毫秒
1.
Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ , where a = n - 3 - , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997 相似文献
2.
Jian‐Liang Wu 《Journal of Graph Theory》1999,31(2):129-134
The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ. The conjecture has been proved to be true for graphs having Δ = 1, 2, 3, 4, 5, 6, 8, 10. Combining these results, we prove in the article that the conjecture is true for planar graphs having Δ(G) ≠ 7. Several related results assuming some conditions on the girth are obtained as well. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 129–134, 1999 相似文献
3.
Combined with the edge-connectivity, this paper investigates the relationship between the edge independence number and upper embeddability. And we obtain the following result: Let G be a k-edge-connected graph with girth g. If α '(G)≤((k-1)2+2) [g/2]+(1-(-1)n)/2((k-1)(k-2)+1)-1,where k=1,2,3, and α(G) denotes the edge independence number of G, then G is upper embeddable and the upper bound is best possible. And it has generalized the relative results. 相似文献
4.
Wiebke Bedenknecht Jie Han Yoshiharu Kohayakawa Guilherme O. Mota 《Random Structures and Algorithms》2019,55(4):795-807
For k ≥ 2 and r ≥ 1 such that k + r ≥ 4, we prove that, for any α > 0, there exists ε > 0 such that the union of an n‐vertex k‐graph with minimum codegree and a binomial random k‐graph with on the same vertex set contains the rth power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft. 相似文献
5.
It is well known that every bipartite graph with vertex classes of size n whose minimum degree is at least n/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect matchings in r‐uniform hypergraphs of large minimum degree. Our bounds on the minimum degree are essentially best possible. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 269–280, 2006 相似文献
6.
7.
8.
9.
Torsten Thiele 《Journal of Graph Theory》1999,30(3):213-221
We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d1(v), d2(v), …) where dm(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σv∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999 相似文献
10.
It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χc(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χc(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000 相似文献
11.
王恺顺 《中国科学A辑(英文版)》2003,46(1):91-93
In this paper, it is proved that the girth of a 4-homogeneous bipartite graph with valency greater than 2 is at most 12. 相似文献
12.
The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs.Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques.This connection provided a new proof of Turán classical result on the Turán density of complete graphs.Since then,Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs.Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range.They showed that if G is a 3-uniform graph with m edges containing a clique of order t-1,then λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).It has been shown that to verify this conjecture for 3-uniform graphs,it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11. 相似文献
13.
14.
We establish lower bounds on the matching number of graphs of given odd regularity d and odd girth g, which are sharp for many values of d and g. For d=g=5, we characterize all extremal graphs. 相似文献
15.
A. Gamburd S. Hoory M. Shahshahani A. Shalev B. Virág 《Random Structures and Algorithms》2009,35(1):100-117
We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (logd‐1|G|)1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??q asymptotically almost surely have girth at least log d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
16.
17.
18.
We introduce a new approach and prove that the maximum number of triangles in a -free graph on vertices is at most We show a connection to -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced--free and -free graph. 相似文献
19.
20.
We show that every n‐vertex cubic graph with girth at least g have domination number at most 0.299871n+ O(n/g)<3n/10 + O(n/g) which improves a previous bound of 0.321216n+ O(n/g) by Rautenbach and Reed. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:131‐142, 2012 相似文献