On long cycles through four prescribed vertices of a polyhedral graph

Jochen Harant; Stanislav Jendrol'; Hansjoachim Walther

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 short cycles through prescribed vertices of a polyhedral graph

Erhard Hexel (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Guaranteed upper bounds on the length of a shortest cycle through k ≤ 5 prescribed vertices of a polyhedral graph or plane triangulation are proved.

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

A note on graph colouring

Dănuţ Marcu (1995)

Czechoslovak Mathematical Journal

Similarity:

A problem concerning $j$ -pancyclic graphs

Vasil Jacoš, Stanislav Jendroľ (1974)

Matematický časopis

Similarity: