Generating Sequences of Clique-Symmetric Graphs via Eulerian Digraphs

Authors

John P. McSorley, Southern Illinois University CarbondaleFollow
Thomas D. Porter, Southern Illinois University Carbondale

Comments

Published in Discrete Mathematics, 287(1-3), 85-91.

Abstract

Let {G_p1,G_p2, . . .} be an infinite sequence of graphs with G_pn having pn vertices. This sequence is called K_p-removable if G_p1 ≅ K_p, and G_pn − S ≅ G_p(n−1) for every n ≥ 2 and every vertex subset S of G_pn that induces a K_p. Each graph in such a sequence has a high degree of symmetry: every way of removing the vertices of any fixed number of disjoint K_p’s yields the same subgraph. Here we construct such sequences using componentwise Eulerian digraphs as generators. The case in which each G_pn is regular is also studied, where Cayley digraphs based on a finite group are used.

Recommended Citation

McSorley, John P. and Porter, Thomas D. "Generating Sequences of Clique-Symmetric Graphs via Eulerian Digraphs." (Oct 2004).