A Polynomial View of Co-adjacency in Graphs.

Abstract

We present a polynomial view of co-adjacency in graphs by introducing the co-adjacent polynomial, a generating function that counts co-adjacent vertex subsets according to their cardinalities. We characterize its basic coefficients, derive explicit formulas for several standard graph classes, and determine its behavior under the join operation. In particular, we prove that the co-adjacent polynomial of the join of two graphs equals the sum of the corresponding polynomials minus one, and extend this identity to arbitrary finite joins. These results establish the co-adjacent polynomial as a graph descriptor associated with common non-neighbor structures.