The λ-Fold Spectrum Problem for the Orientations of the Eight-Cycle
Open Access
Abstract
A D-decomposition of a graph (or digraph) G is a partition of the edge set (or arc set) of G into subsets, where each subset induces a copy of the fixed graph D. Graph decomposition finds motivation in numerous practical applications, particularly in the realm of symmetric graphs, where these decompositions illuminate intricate symmetrical patterns within the graph, aiding in various fields such as network design, and combinatorial mathematics, among various others. Of particular interest is the case where G is , the -fold complete symmetric digraph on v vertices, that is, the digraph with directed edges in each direction between each pair of vertices. For a given digraph D, the set of all values v for which has a D-decomposition is called the -fold spectrum of D. An eight-cycle has 22 non-isomorphic orientations. The -fold spectrum problem has been solved for one of these oriented cycles. In this paper, we provide a complete solution to the -fold spectrum problem for each of the remaining 21 orientations.
Keywords
This publication has 17 references indexed in Scilit:
- Extending the Characteristic Polynomial for Characterization of C20 Fullerene CongenersMathematics, 2017
- Digraphs2009
- Cycle decompositions IV: complete directed graphs and fixed length directed cyclesJournal of Combinatorial Theory, Series A, 2003
- Structural graph matching using the EM algorithm and singular value decompositionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Decomposition of Km,n(Km,n∗) into cycles (circuits) of length 2kJournal of Combinatorial Theory, Series B, 1981
- Decompositions of complete symmetric digraphs into the oriented pentagonsJournal of the Australian Mathematical Society, 1979
- Decompositions of complete symmetric digraphs into the four oriented quadrilaterals1978
- Partition of the edges of the directed complete graph into 4-cyclesDiscrete Mathematics, 1975
- An application of the solution of Kirkman's schoolgirl problem: The decomposition of the symmetric oriented complete graph into 3-circuitsDiscrete Mathematics, 1974
- Directed triple systemsJournal of Combinatorial Theory, Series A, 1973