Closed walks and graphlets

Abstract

We propose a new spectral formula for counting the number of closed walks of certain length at a particular vertex of a graph. The formula is based on the number of spanning closed walks in the connected induced rooted subgraphs of a graph, called graphlets, of particular types. We use the inclusion-exclusion principle for counting the number of spanning closed walks in a rooted graph, and compute the number of spanning closed walks for 73 connected rooted graphs up to five vertices. This investigation is related to the network alignment problem. © 2017 Utilitas Mathematica Publishing Inc.. All rights reserved.