The Library
Hybrid bases in graphs
Tools
Tools
Tools
Novak, Ladislav and Gibbons, Alan (1992) Hybrid bases in graphs. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-211.pdf - Other - Requires a PDF viewer. Download (1980Kb) | Preview |
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.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | March 1992 | ||||
| Dates: |
|
||||
| Number: | Number 211 | ||||
| Number of Pages: | 29 | ||||
| DOI: | CS-RR-211 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 3075 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
