Computer Science – Discrete Mathematics
Scientific paper
2012-02-24
Computer Science
Discrete Mathematics
9 pages, no figures
Scientific paper
We demonstrate that any walk on a directed graph G can be decomposed into an underlying simple path and a nested collection of bare cycles, where simple paths and bare cycles are open and closed walks that are forbidden from visiting any vertex more than once. We define a convention for the nesting structure of the bare cycles that makes this path decomposition unique. In contrast to existing decompositions based on the cycle space of a graph, our walk decomposition natively respects the ordering of the edges in a walk, allowing a natural extension to walks on weighted directed graphs with non-commutative edge weights. We thus show that the sum of all walks on G can be recast as a finite sum over simple paths only. We provide two applications of this result: firstly, we derive a continued-fraction expression for the walk-generating matrix of an arbitrary directed graph, and secondly, we obtain an expression relating the communicability and subgraph centrality of any vertex of G to the communicability and subgraph centrality of vertices in arbitrarily chosen subgraphs of G.
Giscard Pierre-Louis
Jaksch Dieter
Thwaite S. J.
No associations
LandOfFree
A basis for the ensemble of walks on digraphs with non-commuting edge weights does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A basis for the ensemble of walks on digraphs with non-commuting edge weights, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A basis for the ensemble of walks on digraphs with non-commuting edge weights will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-79506