Hamilton Circuits in Tree Graphs
- 1 March 1966
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuit Theory
- Vol. 13 (1) , 82-90
- https://doi.org/10.1109/tct.1966.1082546
Abstract
Two operations for augmenting networks (linear graphs) are defined: edge insertion and vertex insertion. These operations are sufficient to allow the construction of arbitrary nonseparable networks, starting with a simple circuit. The tree graph of a network is defined as a linear graph in which each vertex corresponds to a tree of the network, and each edge corresponds to an elementary tree transformation between trees of the network. A property of tree graphs, referred to as "Property H," is defined: ift_{\alpha}andt_bare two trees of a network, and ift_{\alpha}andt_bare related by an elementary tree transformation, then there exists a Hamilton Circuit through the tree graph such thatt_{\alpha}andt_bare adjacent in the circuit. It is shown that any tree graph containing more than two vertices has Property H.Keywords
This publication has 3 references indexed in Scilit:
- On Coefficients of Polynomials in Network FunctionsIRE Transactions on Circuit Theory, 1960
- The solution of passive electrical networks by means of mathematical treesProceedings of the IEE - Part III: Radio and Communication Engineering, 1953
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932