✦ LIBER ✦

Real flow number and the cycle rank of a graph

✍ Scribed by Robert Lukot'ka; Martin Škoviera

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 101 KB
Volume: 59
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20320

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number p/q + 1, where p and q are two relatively prime numbers must have cycle rank at least p + q − 1. A special case of this result yields that the real flow number of a 2‐connected cubic graph with chromatic index 4 and order at most 8__k__ + 4 is bounded from below by 4 + 1/k. Using this bound we prove that the real flow number of the Isaacs snark I~2__k__ + 1~ equals 4 + 1/k, completing the upper bound due to Steffen [Steffen, J Graph Theory 36 (2001), 24–34]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 11–16, 2008

📜 SIMILAR VOLUMES

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆

Chromatic Number and the 2-Rank of a Gra

Chromatic Number and the 2-Rank of a Graph

✍ C.D. Godsil; Gordon F. Royle 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We show that if the adjacency matrix of a graph X has 2-rank 2r, then the chromatic number of X is at most 2 r +1, and that this bound is tight. 2001

Neighborhood unions and the cycle cover

Neighborhood unions and the cycle cover number of a graph

✍ Guantao Chen; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a

The number of shortest cycles and the ch

The number of shortest cycles and the chromatic uniqueness of a graph

✍ C. P. Teo; K. M. Koh 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB 👁 2 views

## Abstract For a graph __G__, let __g__(__G__) and σ~g~(__G__) denote, respectively, the girth of __G__ and the number of cycles of length __g__(__G__) in __G__. In this paper, we first obtain an upper bound for σ~g~(__G__) and determine the structure of a 2‐connected graph __G__ when σ~g~(__G__)

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 hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro