In a recent work by Beeler and Jamison [1], it is shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As a cycle with at least four vertices is a canonical example of a triangle-free subgraph, we concentrate our efforts on these. In this paper, we will state necessary and sufficient conditions for the existence of edge induced and vertex induced cycles within circulants. We will also use labelling methods to find arbitrary vertex induced subgraphs within circulants.
展开▼
