Premium
Iterating the branching operation on a directed graph
Author(s) -
Athanasiadis Christos A.
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(199703)24:3<257::aid-jgt7>3.0.co;2-o
Subject(s) - combinatorics , mathematics , corollary , conjecture , discrete mathematics , directed graph , graph
The branching operation D , defined by Propp, assigns to any directed graph G another directed graph D ( G ) whose vertices are the oriented rooted spanning trees of the original graph G . We characterize the directed graphs G for which the sequence δ( G ) = ( G, D ( G ), D 2 ( G ),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G , δ( G ) converges if and only if D 2 ( G ) = D ( G ). © 1997 John Wiley & Sons, Inc.