Duality in graph families
type: Item
instance of: scholarly article
title: Duality in graph families
zbMATH Open document ID: 0772.05084
DOI: 10.1016/0012-365X(92)90705-K
author: Hong-Jian Lai
author: Hongyuan Lai
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: The authors investigate some properties of collections of graphs called families. The complete graph family \({\mathcal C}\) is defined as a class of graphs which contains the one-vertex graph \(K_ 1\), is closed under contraction, and satisfies the following condition: \[ \text{if for a subgraph } H\text{ of } G, \quad H\in{\mathcal C},\quad G/H\in{\mathcal C}\text{ then also } G\in{\mathcal C}; \] where \(G/H\) is a contraction of \(G\) with respect to \(H\). A graph family \({\mathcal F}\) is free if it contains \(K_ 1\), is closed under subgraphs, and satisfies the following condition: \[ \text{if for any induced subgraph } H\text{ of } G,\;H\in{\mathcal F},\;G/H\in{\mathcal F}\text{ then also } G\in{\mathcal F}. \] The paper contains several characterization theorems for complete families and free families closed under some supplementary conditions as edge-deletions, edge- contractions etc.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 166358
zbMATH Keywords: duality
zbMATH Keywords: graph families
zbMATH Keywords: complete graph family
zbMATH Keywords: contraction
zbMATH Keywords: free families
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
cites work: Q5422499
cites work: The reduction of graph families closed under contraction
cites work: Q3791179
cites work: Q3032302
cites work: A reduction method to find spanning Eulerian subgraphs
cites work: Double cycle covers and the petersen graph
cites work: Spanning Eulerian subgraphs and matchings
cites work: Q4731211
cites work: Contractions of graphs with no spanning Eulerian subgraphs
cites work: Q3808129
cites work: Fractional arboricity, strength, and principal partitions in graphs and matroids
cites work: Q3974693
cites work: Contractions and hamiltonian line graphs
cites work: On the Hamiltonian index
cites work: Graph whose edges are in small cycles
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Decomposition of Finite Graphs Into Forests
cites work: On the Problem of Decomposing a Graph into n Connected Factors
cites work: Q4111952
description: scientific article; zbMATH DE number 166358