<%@ 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-211

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

L.A. Novak and A.M. Gibbons, Hybrid Bases in Graphs (March 1, 1992).

Abstract

In this paper we introduce a new concept, that of hybrid base, which is a maximal circuitless and cutsetless subset of a graph. Although this concept of simultaneous circuitlessness and cutsetlessness has been used in proofs of some theorems in so called hybrid graph theory, it has not received much attention. Only largest circuitless and cutsetless subsets (hybrid bases of maximum cardinality) have been recognised as important and then only as an auxiliary notion. In contrast to maximally circuitless subsets (trees) or to maximally cutsetless subsets (cotrees), hybrid bases are not of the same cardinality. This fact, although seemingly an "imperfection is the cause of rich structure which we describe in this paper through several propositions. The concept of hybrid bases is related to several important notions in hybrid orientated graph theory. For example, it is related to maximally distant pairs of trees, to complementary pairs of trees, to perfect trees and to topological degree of freedom. It is also closely related to the problem of finding the minimum number of independent variables in the hybrid analysis of electrical networks.

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