Every graph is an induced isopart of a circulant. (English) Zbl 0614.05052

Fink, John Frederick; Ruiz, Sergio

Czech. Math. J. 36(111), 172-176 (1986).

A graph H is an isopart of a graph G if there exist subgraphs \(G_ 1,G_ 2,...,G_ k\) of G such that their edge sets form a partition of the edge set of G and every \(G_ i\) is isomorphic to the graph H. It is proved that every nonempty graph H is an induced isopart of a circulant graph G (i.e. the adjacency matrix of G is circulant). This theorem is applied to digraphs.

Reviewer: M.Demlová

MSC:

05C99

Graph theory

Keywords:

undirected graph; induced graph; graph decomposition; circulant; digraphs

References:

[1]	J. C. Bermond, D. Sotteau: Graph decompositions and G-designs. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, 1975). Congressus Numeratium, No. XV, Utilitas Math., Winnipeg, Man., (1976), 53-72. · Zbl 0331.05021
[2]	J. F. Fink: Every graph is an induced isopart of a connected regular graph. submitted. · Zbl 0614.05052
[3]	F. Harary R. W. Robinson, N. C. Wormald: Isomorphic factorizations V.: Directed graphs. Mathematika 25 (1978), 279-285. · Zbl 0387.05015
[4]	A. Rosa: On certain valuations of the vertices of a graph. Theory of Graphs. Proc. Internat. Sympos. Rome 1966, Gordon and Breach, New York, (1967), 349-355.
[5]	R. M. Wilson: Decomposition of complete graphs into subgraphs isomorphic to a given graph. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, 1975). Congressus Numeratium No XV, Utilitas Math., Winnipeg, Man. (1976), 647-659.