  Entropies based on walks on graphs and on their line-graphs are defined. They
are based on the summation over diagonal and off-diagonal elements of the
thermal Green's function of a graph also known as the communicability. The walk
entropies are strongly related to the walk regularity of graphs and
line-graphs. They are not biased by the graph size and have significantly
better correlation with the inverse participation ratio of the eigenmodes of
the adjacency matrix than other graph entropies. The temperature dependence of
the walk entropies is also discussed. In particular, the walk entropy of graphs
is shown to be non-monotonic for regular but non-walk-regular graphs in
contrast to non-regular graphs.
