Premium
Lambda composition
Author(s) -
Cameron Kathie,
Edmonds Jack
Publication year - 1997
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/(sici)1097-0118(199709)26:1<9::aid-jgt2>3.0.co;2-n
Subject(s) - combinatorics , mathematics , corollary , lambda , graph , graph factorization , discrete mathematics , line graph , voltage graph , physics , optics
A lambda in a graph G is two edges uv and vw such that uw is not an edge. A subgraph A of G is called a lambda‐subgraph if every lambda of G has both or neither of its edges in A . We describe the decomposition of a graph into its lambda subgraphs and use this to prove a decomposition theorem of Gallai ( Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66). A corollary is that a graph is perfect if and only if each of its edge‐minimal lambda subgraphs is. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:9–16, 1997