Walking backward: walk counts of negative order

Area of Science:

• Graph theory
• Mathematical chemistry
• Network analysis

Background:

• Walk counts are used to analyze graph and molecular structures.
• Previous research defined walk counts for positive and infinite orders.
• Lukovits and Trinajstić recently introduced negative-order walk counts.

Purpose of the Study:

• To derive a closed-form formula for negative-order walk counts.
• To explain previously observed phenomena related to negative-order walks.
• To compare negative-order walk counts with those of positive order.

Main Methods:

• Derivation of a closed-form mathematical formula.
• Analysis of graph adjacency matrices and their eigenvalues.
• Comparison of derived formula with existing walk count formulas.

Main Results:

• A closed-form formula for negative-order walk counts was successfully derived.
• The formula simplifies and explains unexpected observations in negative-order walks.
• The derived formula shows strong similarity to formulas for usual (positive-order) walk counts.
• The numerically smallest eigenvalue of the adjacency matrix is crucial for negative-order walks, analogous to the largest eigenvalue for positive-order walks.

Conclusions:

• The derived formula provides a unified approach to understanding walk counts across different orders.
• The study elucidates the distinct mathematical properties governing negative-order walks.
• This work offers new insights into graph and molecular structure analysis using spectral graph theory.