On Circulants Uniquely Characterized by their Independence Polynomials

Abstract

In $[18]$, Farrell and Whitehead investigate circulant graphs that are uniquely characterized by their matching and chromatic polynomials (i.e., graphs that are “matching unique” and “chromatic unique”). They develop a partial classification theorem, by finding all matching unique and chromatic unique circulants on $n$ vertices, for each $n\le 8$. In this paper, we explore circulant graphs that are uniquely characterized by their independence polynomials. We obtain a full classification theorem by proving that a circulant is independence unique if and only if it is the disjoint union of isomorphic complete graphs.