Premium
Spanning arborescences, ingraphs, and outgraphs
Author(s) -
Berman Kenneth A.
Publication year - 1979
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.3190030206
Subject(s) - combinatorics , mathematics , digraph , spanning tree , set (abstract data type) , enhanced data rates for gsm evolution , minimum degree spanning tree , discrete mathematics , computer science , telecommunications , programming language
Abstract An ingraph N is a subgraph of a digraph G whose edge set consists of all the edges of G that are directed into a subset X of the vertices. Set X is the generating set of N. It is proved that G contains a unique even ingraph and this ingraph is generated by the set A of vertices that root an odd number of spanning out arborescences provided A is nonempty. If A is empty, then there exist at least two even ingraphs.