The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Partitions of a graph into cycles containing a specified linear forest”

On long cycles through four prescribed vertices of a polyhedral graph

Jochen Harant, Stanislav Jendrol', Hansjoachim Walther (2008)

Discussiones Mathematicae Graph Theory

Similarity:

For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.

Partitioning a planar graph without chordal 5-cycles into two forests

Yang Wang, Weifan Wang, Jiangxu Kong, Yiqiao Wang (2024)

Czechoslovak Mathematical Journal

Similarity:

It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without chordal 5-cycles can be partitioned into two forests. This extends a result obtained by Raspaud and Wang in 2008.

The cycle-complete graph Ramsey number r(C₅,K₇)

Ingo Schiermeyer (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The cycle-complete graph Ramsey number r(Cₘ,Kₙ) is the smallest integer N such that every graph G of order N contains a cycle Cₘ on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(Cₘ,Kₙ) = (m-1)(n-1)+1 for all m ≥ n ≥ 3 (except r(C₃,K₃) = 6). This conjecture holds for 3 ≤ n ≤ 6. In this paper we will present a proof for r(C₅,K₇) = 25.

Disjoint 5-cycles in a graph

Hong Wang (2012)

Discussiones Mathematicae Graph Theory

Similarity:

We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.

On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph

David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein (2010)

Discussiones Mathematicae Graph Theory

Similarity:

We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

Fatima Affif Chaouche, Carrie G. Rutherford, Robin W. Whitty (2015)

Discussiones Mathematicae Graph Theory

Similarity:

It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of ∩(n1/k) on the growth rate.