Parallel concepts in graph theory. (English) Zbl 0797.05064

Harary, F.

Math. Comput. Modelling 18, No. 7, 101-105 (1993).

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

Keywords:

Steiner triple systems; 1-factor; perfect matching; edge coloring; stars; galaxy; cluster; triangles

References:

[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)
[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)
[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