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.

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

Displaying similar documents to “On long cycles through four prescribed vertices of a polyhedral graph”

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...

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.

Vertex-dominating cycles in 2-connected bipartite graphs

Tomoki Yamashita (2007)

Discussiones Mathematicae Graph Theory

Similarity:

A cycle C is a vertex-dominating cycle if every vertex is adjacent to some vertex of C. Bondy and Fan [4] showed that if G is a 2-connected graph with δ(G) ≥ 1/3(|V(G)| - 4), then G has a vertex-dominating cycle. In this paper, we prove that if G is a 2-connected bipartite graph with partite sets V₁ and V₂ such that δ(G) ≥ 1/3(max{|V₁|,|V₂|} + 1), then G has a vertex-dominating cycle.

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...