✦ LIBER ✦

Cycles in the complement of a tree or other graph

✍ Scribed by F.C. Holroyd; W.J.G. Wingate

Book ID: 104113604
Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 745 KB
Volume: 55
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(85)80003-0

No coin nor oath required. For personal study only.

✦ Synopsis

Formulas are obtained for the number of m-cycles, y,(G, n), and the number of all cycles, -r(G, n). in the complement of a graph G with respect to the complete graph K,, in terms of the 'linear forest array' of G. Some elementary properties of these arrays are obtained. Computer results are reported which show that, as T ranges over all trees of order p, the star graph maximizes v(T, p) for p = 5 to 8 and the path maximizes r(T, p) for p =9 to 12. This corroborates a conjecture of K.B. Reid. An asymptotic result is proved, comparing y,(F, n) with -r.,(G, n) and y(F, n) with -r(G, n) as n + m for fixed F, G. Finally, if F is a forest it is shown that the computational complexity of calculating -r,(F, n) and y(F, n) is polynomially bounded in the number of edges of F.

📜 SIMILAR VOLUMES

The number of cycles in a hamilton graph

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

On the Existence of Disjoint Cycles in a

On the Existence of Disjoint Cycles in a Graph

✍ Hikoe Enomoto 📂 Article 📅 1998 🏛 Springer-Verlag 🌐 English ⚖ 129 KB

Estimations for the number of cycles in

Estimations for the number of cycles in a graph

✍ Lutz Volkmann 📂 Article 📅 1996 🏛 Springer Netherlands 🌐 English ⚖ 379 KB

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 minimum number of subgraphs in a gra

The minimum number of subgraphs in a graph and its complement

✍ Lane Clark 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent