## Parallel concepts in graph theory.(English)Zbl 0797.05064

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.
Reviewer: J.Dinitz

### MSC:

 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C15 Coloring of graphs and hypergraphs 05B15 Orthogonal arrays, Latin squares, Room squares 05C35 Extremal problems in graph theory 05C38 Paths and cycles
Full Text:

### References:

  Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0797.05064  Harary, F.; Plantholt, M., Minimum maximal graphs with forbidden subgraphs, Math. Slovaca, 8, 191-193 (1984)  Harary, F.; Plantholt, M., Minimum and maximum, minimal and maximal: Connectivity, Bull. Bombay Math. Colloq., 4, 1-5 (1986)  Harary, F.; Norman, R.; Cartwright, D., Structural Models: An Introduction to the Theory of Directed Graphs (1965), Wiley: Wiley New York · Zbl 0139.41503  Harary, F.; Robinson, R. W.; Wormald, N., Isomorphic factorizations I: Complete graphs, Trans. Amer. Math. Soc., 242, 243-260 (1978) · Zbl 0381.05044  Harary, F.; Wallis, W. D., Isomorphic factorizations II: Combinatorial designs, Congressus Numerantium, 19, 13-28 (1978)  Harary, F.; Robinson, R. W., Isomorphic factorizations X: Unsolved problems, J. Graph Theory, 9, 67-86 (1985) · Zbl 0617.05051  Archdeacon, D.; Dinitz, J.; Harary, F., Orthogonal edge colorings of graphs, Congressus Numerantium, 47, 49-67 (1985)  Dénes, J.; Keedwell, A. D., Latin Squares and Their Applications (1974), Academic: Academic New York · Zbl 0283.05014  Fiorini, S.; Wilson, R. J., Edge Colourings of Graphs (1977), Pitman: Pitman London · Zbl 0421.05023  Harary, F.; Hsu, D. F., Node graceful graphs, Comput. Math. Appl., 15, 291-298 (1988) · Zbl 0648.05050  Harary, F., Covering and packing in graphs I, Annals N.Y. Acad. Sci., 175, 198-205 (1970) · Zbl 0226.05119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.