首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 250 毫秒
1.
Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209-218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h?g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.  相似文献   

2.
A (k;g)‐cage is a k‐regular graph with girth g and with the least possible number of vertices. In this paper, we prove that (k;g)‐cages are k‐edge‐connected if g is even. Earlier, Wang, Xu, and Wang proved that (k;g)‐cages are k‐edge‐connected if g is odd. Combining our results, we conclude that the (k;g)‐cages are k‐edge‐connected. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 219–227, 2005  相似文献   

3.
The odd girth of a graph G is the length of a shortest odd cycle in G. Let d(n, g) denote the largest k such that there exists a k-regular graph of order n and odd girth g. It is shown that dn, g ≥ 2|n/g≥ if n ≥ 2g. As a consequence, we prove a conjecture of Pullman and Wormald, which says that there exists a 2j-regular graph of order n and odd girth g if and only if ngj, where g ≥ 5 is odd and j ≥ 2. A different variation of the problem is also discussed.  相似文献   

4.
Motivated by the work of Ne?et?il and Rödl on “Partitions of vertices” we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number r and a graph G of order m with odd girth g, we show the existence of a graph H with odd girth at least g and order that is polynomial in m such that every r‐coloring of the vertices of H yields a monochromatic and induced copy of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 255‐264, 2011  相似文献   

5.
In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.  相似文献   

6.
We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C4‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003  相似文献   

7.
Recently, Mader [ 7 ] proved that every 2k‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004  相似文献   

8.
The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000  相似文献   

9.
In this article, we establish bounds for the length of a longest cycle C in a 2‐connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1) δ + t. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 107–127, 1999  相似文献   

10.
11.
In this article we study multipartite Ramsey numbers for odd cycles. Our main result is the proof that a conjecture of Gyárfás et al. (J Graph Theory 61 (2009), 12–21), holds for graphs with a large enough number of vertices. Precisely, there exists n0 such that if n?n0 is a positive odd integer then any two‐coloring of the edges of the complete five‐partite graph K(n ? 1)/2, (n ? 1)/2, (n ? 1)/2, (n ? 1)/2, 1 contains a monochromatic cycle of length n. © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

12.
A g cage of valency k is a regular graph of girth g and valency k with the minimum number of vertices consistent with this condition [12]. An embeddable g net of valency k corresponds to a graph of girth g which can be drawn on a surface in such a way that every face is bounded by a circuit of length g. Similarities between g nets and known g cages are investigated and a possible 5 cage of valency 6 is produced. An existence theorem for regular g nets is also given.  相似文献   

13.
Harary and Kovacs [Smallest graphs with given girth pair, Caribbean J. Math. 1 (1982) 24-26] have introduced a generalization of the standard cage question—r-regular graphs with given odd and even girth pair. The pair (ω,ε) is the girth pair of graph G if the shortest odd and even cycles of G have lengths ω and ε, respectively, and denote the number of vertices in the (r,ω,ε)-cage by f(r,ω,ε). Campbell [On the face pair of cubic planar graph, Utilitas Math. 48 (1995) 145-153] looks only at planar graphs and considers odd and even faces rather than odd and even cycles. He has shown that f(3,ω,4)=2ω and the bounds for the left cases. In this paper, we show the values of f(r,ω,ε) for the left cases where (r,ω,ε)∈{(3,3,ε),(4,3,ε),(5,3,ε), (3,5,ε)}.  相似文献   

14.
An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K4‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K4‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {Hn} of such graphs with limn→∞χc(Hn)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010  相似文献   

15.
For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph Kn of order n. For example, it is shown that for all odd n ≥ 11, Kn has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph KnI obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.  相似文献   

16.
Our main result is the following theorem. Let k ≥ 2 be an integer, G be a graph of sufficiently large order n, and δ(G) ≥ n/k. Then:
  • (i) G contains a cycle of length t for every even integer t ∈ [4, δ(G) + 1].
  • (ii) If G is nonbipartite then G contains a cycle of length t for every odd integer t ∈ [2k ? 1, δ(G) + 1], unless k ≥ 6 and G belongs to a known exceptional class.
© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 157–170, 2006  相似文献   

17.
We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1 ). Hopkins and Staton [J Graph Theory 6(2) (1982), 115–121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477–504] proved that every (sub)cubic graph of girth at least 4 has an edge‐cut containing at least of the edges. The existence of such an edge‐cut follows immediately from the existence of a 5‐edge‐coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above‐described 5‐edge‐coloring; hence our theorem may also be viewed as a weak version of Ne?et?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C5). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011  相似文献   

18.
(k;g) -笼是指具有围长 g的 k-正则图中那些顶点数最小的图 .文 [2 ]中有下面的猜想 :设 G为一个 ( k;g) -笼 ,则它的每一个 g-圈 C是不可分离的 ( nonseparating) ,也就是说 ,对 G中任意的 g-圈 C,G- C仍是连通的 .对于偶数 g,[2 ]已给出了此猜想的证明 .本文中 ,证明 :对于奇数 g,此猜想也是正确的 .  相似文献   

19.
In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1.  相似文献   

20.
We show that the size of a smallest connected k-regular graph with girth pair (4, 2l + 1) is within a constant of (2l + 1) k/2. In so doing we disprove a conjecture of Harary and Kovacs.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号