The number of walks from one vertex to another in a finite graph can be counted by the adjacency matrix. In this paper, we prove two theorems that connect the graph Laplacian with two types of walks in a graph. By defining two types of walks and giving orientation to a finite graph, one can easily count the number of the total signs of each kind of walk from one element to another of a fixed length.

Author Bio

Chengzheng Yu graduated from University of Illinois at Urbana-Champaign in May 2017, with High Distinction in Mathematics and a second major in Economics. He will obtain a Master’s degree at Georgetown University in Aug 2018, and expects to earn a PhD focusing on quantitative applied economics in the coming future. His mathematical research interests include combinatorics, topology, linear algebra, and their applications. He completed this paper in Dec 2016 as one part of the Illinois Geometry Lab (IGL) project titled Quantum mechanics for Graphs and CW-complexes, under the supervision of Professor Ivan Contreras. This project lasted for one academic year (Aug 2016 - Jun 2017), and was awarded Illinois Geometry Lab Research Award – First Place in April 2017. He and Professor Contreras completed and submitted another paper, Hyperwalk Formulae for Even and Odd Laplacians in Finite CW-Hypergraphs, in Jul 2017.