Premium
Superperfect pairs of trees in graphs
Author(s) -
Novak Ladislav A.,
Gibbons Alan
Publication year - 1993
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.4490210207
Subject(s) - citation , library science , computer science , information retrieval
The notion of a superperfect pair of trees is introduced and characterized in detail. It is closely related to the well known notion of a maximally distant pair of trees as well as to some other recently introduced notions such as perfect pairs of trees and hybrid bases. We show (Propositions 1 and 2) that every maximally distant pair is a superperfect pair of trees and every superperfect pairs of trees is a perfect pair of trees. A central result is contained in Theorem 1 which states that a pair of trees (t1,t2) is a superperfect pair of trees iff both set differences and t1\t2and t2\t1 are hybrid bases. An algorithm for finding a superperfect pair, starting with an arbitrary tree, is also described.