𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Note on graphs without repeated cycle lengths

✍ Scribed by Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E.

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
225 KB
Volume
29
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general case.

📜 SIMILAR VOLUMES

Planar Graphs Without Cycles of Specific
Planar Graphs Without Cycles of Specific Lengths
✍ G. Fijavž; M. Juvan; B. Mohar; R. Škrekovski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles.

A note on shortest cycle covers of cubic
A note on shortest cycle covers of cubic graphs
✍ Xinmin Hou; Cun-Quan Zhang 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract Let __SCC__~3~(__G__) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph __G__. It is proved in this note that if __G__ contains no circuit of length 5 (an improvement of Jackson's (__JCTB 1994__) result: if __G__ has girth at least 7) and if all 5‐circuits of __G_

A note on path and cycle decompositions
A note on path and cycle decompositions of graphs
✍ Dom Decaen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

## Abstract In the study of decompositions of graphs into paths and cycles, the following questions have arisen: Is it true that every graph __G__ has a smallest path (resp. path‐cycle) decomposition __P__ such that every odd vertex of __G__ is the endpoint of exactly one path of __P__? This note g

On graphs and algebraic graphs that do n
On graphs and algebraic graphs that do not contain cycles of length 4
✍ Noga Alon; H. Tracy Hall; Christian Knauer; Rom Pinchasi; Raphael Yuster 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

We consider extremal problems for algebraic graphs, that is, graphs whose vertices correspond to vectors in R d , where two vectors are connected by an edge according to an algebraic condition. We also derive a lower bound on the rank of the adjacency matrix of a general abstract graph using the num

A Note on Alternating Cycles in Edge-Col
A Note on Alternating Cycles in Edge-Coloured Graphs
✍ Anders Yeo 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 431 KB

Grossman and Ha ggkvist gave a sufficient condition under which a two-edgecoloured graph must have an alternating cycle (i.e., a cycle in which no two consecutive edges have the same colour). We extend their result to edge-coloured graphs with any number of colours. That is, we show that if there is

Cycles in a graph whose lengths differ b
Cycles in a graph whose lengths differ by one or two
✍ Bondy, J. A.; Vince, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 2 views

Several problems concerning the distribution of cycle lengths in a graph have been proposed by P. Erdös and colleagues. In this note two variations of the following such question are answered. In a simple graph where every vertex has degree at least three, must there exist two cycles whose lengths d