Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pancyclic graph

Sortuj według:

Ogranicz wyniki do:

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

100%

Affif Chaouche F., Rutherford C. G., Whitty R. W.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 3

533-539

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.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Strongly pancyclic and dual-pancyclic graphs

88%

McKee T.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 1

5-14

Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with respect to almost containment. Much of this carries over from graphic to cographic matroids; the resulting 'dual-pancyclic' graphs are shown to be exactly the 3-regular dual-chordal graphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Affif Chaouche F.

1 McKee T.

1 Rutherford C. G.

1 Whitty R. W.

1 2015

1 2009

Wyniki wyszukiwania

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

Strongly pancyclic and dual-pancyclic graphs