✦ LIBER ✦

Cyclicity of graphs

✍ Scribed by Hammack, Richard

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 318 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199910)32:2<160::aid-jgt6>3.0.co;2-u

No coin nor oath required. For personal study only.

✦ Synopsis

The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including chordal graphs, complete n-partite graphs, n-cubes, products of trees and cycles, and planar graphs.

📜 SIMILAR VOLUMES

Graphs omitting sums of complete graphs

✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 1 views

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m • K n )-free graphs such that every countable (m • K n )-free graph occurs as an induced subgraph of one of the graphs G i .

Embedding of graphs in two-irregular gra

Embedding of graphs in two-irregular graphs

✍ M. Axenovich; Z. Füredi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 1 views

Niche graphs and mixed pair graphs of to

Niche graphs and mixed pair graphs of tournaments

✍ Bowser, Steve; Cable, Charles; Lundgren, Richard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB 👁 2 views

In our efforts to study the niche graph of a tournament T , we have found it easier to study the complement, which we call the ''mixed pair'' graph of T and denote MP (T ). We show that an undirected graph G is MP (T ), for some tournament T , if and only if G is one of the following: a cycle of odd

Deza graphs: A generalization of strongl

Deza graphs: A generalization of strongly regular graph

✍ M. Erickson; S. Fernando; W. H. Haemers; D. Hardy; J. Hemmeter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

Decomposing large graphs with small grap

Decomposing large graphs with small graphs of high density

✍ Yuster, Raphael 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 1 views

It is shown that for every positive integer h, and for every > 0, there are graphs H = (V H , E H ) with at least h vertices and with density at least 0.5with the following property: any graph with minimum degree at least |V G | 2 (1 + o(1)) and |E H | divides |E G |, then G has an H-decomposition.

Star partitions of graphs

✍ Egawa, Y.; Kano, M.; Kelmans, Alexander K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB 👁 1 views

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition , and (ii) for every subset S of V (G), G \ S has at most n|S| components with the property that each of their blocks is an odd order complete graph.