Path decompositions of chains and circuits

ABSTRACT. Expressions for the path polynomials (see Farrell [I]) of chains and cir-cuits are derived. These polynomials are then used to deduce results about node dis-joint path decompositions of chains and circuits. Some results are also given for de-compositions in which specific paths must be used. KEY WORDS AND PHRASES. Path polynomial, path decomposition, incorporated graph, etriced decomposition. 1980 MATHEMATICS SUBJECT CLASSIFICATION CODES. 05C38, 05A15. i. INTRODUCTION. The graphs considered here will be finite, undirected and without loops or multi-ple edges. Let G he such a graph. With every path in G, let us associate the weight w With every spanning subgraph C of G consisting of paths l,e2,...,k, let us asso