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