<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-239

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

L.A. Novak and A.M. Gibbons, Superperfect Pairs of Trees in Graphs (February 1, 1993).

Abstract

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\t2 and t2\t1 are hybrid bases. An algorithm for finding a superperfect pair, starting with an arbitrary tree, is also described.

<%@ include file="cited.html" %>

L.A. Novak and A.M. Gibbons, "Superperfect Pairs of Trees in Graphs", International journal of Circuit Theory and Applications 21, pp. 183-189 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>