✦ LIBER ✦

Construction of graphs with given circular flow numbers

✍ Scribed by Zhishi Pan; Xuding Zhu

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 158 KB
Volume: 43
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10124

No coin nor oath required. For personal study only.

✦ Synopsis

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) = 0$. The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003

📜 SIMILAR VOLUMES

Snarks with given real flow numbers

✍ Robert Lukot'ka; Martin Škoviera 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB

We show that for each rational number r such that 4<r ≤ 5 there exist infinitely many cyclically 4-edge-connected cubic graphs of chromatic index 4 and girth at least 5-that is, snarks-whose flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circula

The maximum interval number of graphs wi

The maximum interval number of graphs with given genus

✍ Edward R. Scheinerman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

On local connectivity of graphs with giv

On local connectivity of graphs with given clique number

✍ Andreas Holtkamp; Lutz Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract For a vertex __v__ of a graph __G__, we denote by __d__(__v__) the __degree__ of __v__. The __local connectivity__ κ(__u, v__) of two vertices __u__ and __v__ in a graph __G__ is the maximum number of internally disjoint __u__ –__v__ paths in __G__, and the __connectivity__ of __G__ is

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

Circular flow numbers of regular multigr

Circular flow numbers of regular multigraphs

✍ Eckhard Steffen 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

The circular ¯ow number F c (G) of a graph G (V,E) is the minimum r P Q such that G admits a ¯ow 0 with 1 0 (e) r À 1, for each e P E. We determine the circular ¯ow number of some regular multigraphs. In particular, we characterize the bipartite (2t 1)-regular graphs (t ! 1). Our results imply that

Circular Chromatic Numbers and Fractiona

Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs

✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for