Displaying similar documents to “Union of all the minimum cycle bases of a graph.”

Minimal cycle bases of the lexicographic product of graphs

M.M.M. Jaradat (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A construction of minimum cycle bases of the lexicographic product of graphs is presented. Moreover, the length of a longest cycle of a minimal cycle basis is determined.

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.

Circuit bases of strongly connected digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler (2003)

Discussiones Mathematicae Graph Theory

Similarity:

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.

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.

Edge cycle extendable graphs

Terry A. McKee (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.