Displaying similar documents to “Cycles through specified vertices in triangle-free graphs”

Forbidden Pairs and (k,m)-Pancyclicity

Charles Brian Crane (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs...

On the Erdős-Gyárfás Conjecture in Claw-Free Graphs

Pouria Salehi Nowbandegani, Hossein Esfandiari, Mohammad Hassan Shirdareh Haghighi, Khodakhast Bibak (2014)

Discussiones Mathematicae Graph Theory

Similarity:

The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs

Heavy Subgraph Conditions for Longest Cycles to Be Heavy in Graphs

Binlong Lia, Shenggui Zhang (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices. A vertex of G with degree at least n/2 is called a heavy vertex, and a cycle of G which contains all the heavy vertices of G is called a heavy cycle. In this note, we characterize graphs which contain no heavy cycles. For a given graph H, we say that G is H-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n. We find all the connected graphs S such that a 2-connected graph G being S-heavy implies...

Large Degree Vertices in Longest Cycles of Graphs, I

Binlong Li, Liming Xiong, Jun Yin (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.

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.

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.

A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs

Wojciech Wide (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2. For a given graph H we say that G is H-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies that at least one of them is super-heavy. For a family of graphs H we say that G is H-f1-heavy, if G is H-f1-heavy for...

On hypergraphs of girth five.

Lazebnik, Felix, Verstraëte, Jacques (2003)

The Electronic Journal of Combinatorics [electronic only]

Similarity: