Some Properties of Multicolored-Branch Graphs

Abstract

A multicolored-branch graph is such a linear graph that the branches of the graph are partitioned into several sets, and a certain color is assigned to the branches belonging to each of the sets. The assignment is called a coloring. The degree of interference of loops or cutsets in such a graph is deffned to be the minimum number of indenpedent loops or cutsets respectively containing all the colors. The maximum of the degree of interference taken over all the possible colorings is studied. Theorems concerning the colorings to give the maximum in a two-colored-branch graph are derived. Moreover, the maximum of the degree of interference is shown to be equal to the topological degree of freedom and to the maximum distance between a pair of trees in the graph. The degree of interference is also related to the rank of a certain submatrix of the fundamental loop or cutset matrix. An upper bound and a lower bound on the degree of interference in a three-colored-branch graph are given.