Premium
Perfect pairs of trees in graphs
Author(s) -
Novak Ladislav,
Gibbons Alan
Publication year - 1992
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.4490200206
Subject(s) - symmetrization , mathematics , lemma (botany) , generalization , graph , combinatorics , discrete mathematics , perfect graph theorem , relation (database) , line graph , computer science , pathwidth , ecology , mathematical analysis , poaceae , database , biology
We introduce the concept of perfect pairs of trees of a graph as a natural generalization of so‐called maximally distant pairs of trees. Several propositions and remarks are presented to display the properties of this new notion. Lemma 1, which plays a central role, gives five equivalent statements characterizing the relation ‘to be maximally distant from’ between pairs of trees. Symmetrization of this relation leads to our concept of a perfect pair of trees, the properties of which are given in Theorem 1. Remark 4 shows how naturally our new concept arises. Additionally, certain examples are provided to illustrate perfect pair structures in a graph.