Counting all Parity Realizable Trees

The parity dimension of a graph \( G \) is defined as the dimension of the null space of its closed neighborhood matrix \( N \). A graph with parity dimension \( 0 \) is called all parity realizable (APR). In this paper, a simple recursive procedure for calculating the parity dimension of a tree is given, which is more apt to be used in the context of enumeration than the graph-theoretical characterizations due to Amin, Slater, and Zhang. Applying the recursive relation, we find asymptotic formulas for the number of APR trees and for the average parity dimension of a tree.