Displaying similar documents to “Graphs which have pancyclic complements.”

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

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

Star-Cycle Factors of Graphs

Yoshimi Egawa, Mikio Kano, Zheng Yan (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S...

Characterization of semientire graphs with crossing number 2

D. G. Akka, J. K. Bano (2002)

Mathematica Bohemica

Similarity:

The purpose of this paper is to give characterizations of graphs whose vertex-semientire graphs and edge-semientire graphs have crossing number 2. In addition, we establish necessary and sufficient conditions in terms of forbidden subgraphs for vertex-semientire graphs and edge-semientire graphs to have crossing number 2.