The number of walks in a graph

✍ Scribed by A Dress; I Gutman

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 349 KB
• Volume: 16
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/s0893-9659(03)00085-5

✦ Synopsis

The aim of this note is to call attention to a simple regularity regarding the number of walks in a finite graph G. Let wk denote the number of walks of length k(> 0) in G. Then Wi+,, 5 W&Wzb holds for all a, b E NJ while equality holds exclusively either (I) for all a, b E No (in case G is a regular graph), or (II) for all a, b E N, or (III) for all a, b E NO of equal parity (provided G is connected, this holds if and only if G is nonregular, yet semiregular graph), or (IV) for all a, b E N of equal parity, or (V) just for a = b only.

We show that all of these five cases can actually occur and discuss the resulting classification graphs in exactly five classes.