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


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: DOI


[1] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0797.05064
[2] Harary, F.; Plantholt, M., Minimum maximal graphs with forbidden subgraphs, Math. Slovaca, 8, 191-193 (1984)
[3] Harary, F.; Plantholt, M., Minimum and maximum, minimal and maximal: Connectivity, Bull. Bombay Math. Colloq., 4, 1-5 (1986)
[4] Harary, F.; Norman, R.; Cartwright, D., Structural Models: An Introduction to the Theory of Directed Graphs (1965), Wiley: Wiley New York · Zbl 0139.41503
[5] Harary, F.; Robinson, R. W.; Wormald, N., Isomorphic factorizations I: Complete graphs, Trans. Amer. Math. Soc., 242, 243-260 (1978) · Zbl 0381.05044
[6] Harary, F.; Wallis, W. D., Isomorphic factorizations II: Combinatorial designs, Congressus Numerantium, 19, 13-28 (1978) · Zbl 0405.05016
[7] Harary, F.; Robinson, R. W., Isomorphic factorizations X: Unsolved problems, J. Graph Theory, 9, 67-86 (1985) · Zbl 0617.05051
[8] Archdeacon, D.; Dinitz, J.; Harary, F., Orthogonal edge colorings of graphs, Congressus Numerantium, 47, 49-67 (1985) · Zbl 0622.05023
[9] Dénes, J.; Keedwell, A. D., Latin Squares and Their Applications (1974), Academic: Academic New York · Zbl 0283.05014
[10] Fiorini, S.; Wilson, R. J., Edge Colourings of Graphs (1977), Pitman: Pitman London · Zbl 0421.05023
[11] Harary, F.; Hsu, D. F., Node graceful graphs, Comput. Math. Appl., 15, 291-298 (1988) · Zbl 0648.05050
[12] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.