✦ LIBER ✦

A polynomial bound on the number of light cycles in an undirected graph

✍ Scribed by Ashok Subramanian

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 386 KB
Volume: 53
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)00202-a

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A polynomial bound on the number of ligh

A polynomial bound on the number of light cycles in an undirected graph: Information processing letters 53 (4) (24 February 1995) 173–176

✍ Ashok Subramanian 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 42 KB

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

On the number of hamilton cycles in a ra

On the number of hamilton cycles in a random graph

✍ C. Cooper; A. M. Frieze 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 576 KB

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n)('-')" distinct hamilton cycles for any fixed E > 0.

The number of cycles in a hamilton graph

✍ Yongbing Shi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 523 KB

An improved edge bound on the interval n

An improved edge bound on the interval number of a graph

✍ Jeremy R. Spinrad; G. Vijayan; Douglas B. West 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a