2015/04/28 by Asbjørn Brændeland, Brændeland, Asbjørn
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1504.07626
The definition of 'ordered SBE-tree' has been added. This corrects an omission in the previous versions but does not change anything essential. Some changes have been made to accommodate the addition, and others have been made to correct minor errors and improve wordings
openalex publication_date 2015/04/28 · arxiv created 2015/05/13 · arxiv updated 2015/05/14 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
A split-by-edges tree of a graph G on n vertices is a binary tree T where the root = V(G), every leaf is an independent set in G, and for every other node N in T with children L and R there is a pair of vertices u, v in N such that L = N - v, R = N - u, and uv is an edge in G. It follows from the definition that every maximal independent set in G is a leaf in T, and the maximum independent sets of G are the leaves closest to the root of T.