2005/02/25 by Alastair Farrugia, Peter Mihók, R. Bruce Richter +1 · 9 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Combinatorics #Mathematics #Partition (number theory) #Disjoint sets #Factorization #Graph #Discrete mathematics #Algorithm
paper · pdf · doi:10.1002/jgt.20062
published in Journal of Graph Theory 49(1), 11-27 (Wiley)
openalex publication_date 2005/02/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/06/11
Abstract An Erratum has been published for this article in Journal of Graph Theory 50:261, 2005 . A graph property (i.e., a set of graphs) is hereditary (respectively, induced‐hereditary) if it is closed under taking subgraphs (resp., induced‐subgraphs), while the property is additive if it is closed under disjoint unions. If \cal P and \cal Q are properties, the product \cal P∘ \cal Q consists of all graphs G for which there is a partition of the vertex set of G into (possibly empty) subsets A and B with G [ A ] ∈ \cal P and G [ B ] ∈ \cal Q . A property is reducible if it is the product of two other properties, and irreducible otherwise. We show that very few reducible induced‐hereditary properties have a unique factorization into irreducibles, and we describe them completely. On the other hand, we give a new and simpler proof that additive hereditary properties have a unique factorization into irreducible additive hereditary properties [ J. Graph Theory 33 (2000), 44–53]. We also introduce analogs of additive induced‐hereditary properties, and characterize them in the style of Scheinerman [ Discrete Math . 55 (1985), 185–193]. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 11–27, 2005