z-logo
Premium
Real flow number and the cycle rank of a graph
Author(s) -
Lukot'ka Robert,
Škoviera Martin
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20320
Subject(s) - mathematics , combinatorics , graph , upper and lower bounds , bounded function , cubic graph , petersen graph , discrete mathematics , graph power , voltage graph , line graph , mathematical analysis
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom