Premium
Greedoids from flames
Author(s) -
Joó Attila
Publication year - 2021
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.22681
Subject(s) - digraph , generalization , mathematics , combinatorics , enhanced data rates for gsm evolution , polynomial , degree (music) , discrete mathematics , computer science , mathematical analysis , physics , telecommunications , acoustics
A digraph D with r ∈ V ( D ) is an r ‐flame if for every v ∈ V ( D ) − r , the in‐degree of v is equal to the local edge‐connectivity λ D ( r , v ) . We show that for every digraph D and r ∈ V ( D ) , the edge sets of the r ‐flame subgraphs of D form a greedoid. Our method yields a new proof of Lovász's theorem stating: for every digraph D and r ∈ V ( D ) , there is an r ‐flame subdigraph F of D such that λ F ( r , v ) = λ D ( r , v ) for v ∈ V ( D ) − r . We also give a strongly polynomial algorithm to find such an F working with a fractional generalization of Lovász's theorem.