𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nonseparable graphs with a given number of cycles

✍ Scribed by Ranko Šćepanović; Gerhard Ringel; Dragan Marušič; G. L. Chia; Brian Alspach

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
646 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

G. Ringel conjectured that for every positive integer n other than 2, 4, 5, 8, 9, and 16, there exists a nonseparable graph with n cycles. It is proved here that the conjecture is true even with the restriction to planar and hamiltonian graphs.

📜 SIMILAR VOLUMES

The number of connected sparsely edged g
The number of connected sparsely edged graphs. IV large nonseparable graphs
✍ E. M. Wright 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB

The number of nonseparable graphs on n labeled points and q lines is u(n, 9). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n + 30. Here an asymptotic approximatio

Construction of graphs with given circul
Construction of graphs with given circular flow numbers
✍ Zhishi Pan; Xuding Zhu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB 👁 1 views

## Abstract Suppose __r__ ≥ 2 is a real number. A proper __r__‐flow of a directed multi‐graph $\vec {G}=(V, E)$ is a mapping $f: E \to R$ such that (i) for every edge $e \in E$, $1 \leq |f(e)| \leq r-1$; (ii) for every vertex ${v} \in V$, $\sum \_{e \in E^{+(v)}}f(e) - \sum \_{e \in E^{-(v)}}f(e) =

Covering a graph with cycles passing thr
Covering a graph with cycles passing through given edges
✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 2 views

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi

Four-cycles in graphs without a given ev
Four-cycles in graphs without a given even cycle
✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

We prove that every bipartite C 2' -free graph G contains a C 4free subgraph H with e(H) ! e(G)=(' À 1). The factor 1=(' À 1) is best possible. This implies that ex(n; C 2' ) 2(' À 1)ex(n; fC 4 ; C 2' g), which settles a special case of a conjecture of Erdo ˝s and Simonovits.

On connectivity in graphs with given cli
On connectivity in graphs with given clique number
✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

## Abstract We consider finite, undirected, and simple graphs __G__ of order __n__(__G__) and minimum degree δ(__G__). The connectivity κ(__G__) for a connected graph __G__ is defined as the minimum cardinality over all vertex‐cuts. If κ(__G__) < δ(__G__), then Topp and Volkmann 7 showed in 1993 f