Graph family operations

In previous papers, Catlin introduced four functions, denoted S O , S R , S C , and S H , between sets of finite graphs. These functions proved to be very useful in establishing properties of several classes of graphs, including supereulerian graphs and graphs with nowhere zero k-flows for a fixed i...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2001-03, Vol.230 (1), p.71-97
Main Authors: M. Hobbs, Arthur, Lai, Hong-Jian, A. Catlin, Paul
Format: Article
Language:English
Subjects:
Complete family
Free family
Graph family
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In previous papers, Catlin introduced four functions, denoted S O , S R , S C , and S H , between sets of finite graphs. These functions proved to be very useful in establishing properties of several classes of graphs, including supereulerian graphs and graphs with nowhere zero k-flows for a fixed integer k⩾3. Unfortunately, a subtle error caused several theorems previously published in Catlin (Discrete Math. 160 (1996) 67–80) to be incorrect. In this paper we correct those errors and further explore the relations between these functions, showing that there is a sort of duality between them and that they act as inverses of one another on certain sets of graphs.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(00)00071-6