Parallel concepts in graph theory (Q1324287): Difference between revisions

One edge of a graph \(G\) is taken as a basic unit, regarded as the set of its two nodes. Two edges are called parallel (or independent) if they are disjoint. Then a 1-factor (or perfect matching) of \(G\) is a spanning set of parallel edges. A 1-factorization of \(G\) is a partition of its edge set \(E(G)\) into 1-factors, each of which is considered as a color class in a proper edge coloring of \(G\). Then two edge colorings of \(G\) are called orthogonal if no two edges with the same first coloring have the same second coloring. Motivated by parallel processing computers, this paper proposes the hierarchy of parallel structures in a graph consisting of (1) an edge, (2) a set of parallel edges, (3) a collection of parallel sets of edges, (4) a class of such orthogonal collections. Also mentioned is a hierarchy for stars namely, (1) an edge, (2) a star, \(K_{1,n}\), (3) a galaxy, a set of disjoint stars and (4) a cluster, a collection of galaxies. Further hierarchies are given for triangles (Steiner triple systems) and paths. Several questions are mentioned, but no theorems are proved.