×

zbMATH — the first resource for mathematics

Every graph is an induced isopart of a circulant. (English) Zbl 0614.05052
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
PDF BibTeX XML Cite
Full Text: EuDML
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.
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.