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 \leq 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.