In this paper, an SIS (susceptible-infected-susceptible)-type epidemic propagation isstudied on a special class of 3-regular graphs, called modified cycle graphs. The modifiedcycle graph is constructed from a cycle graph with N nodes by connecting nodei to thenode i +d in a way that every node has exactly three links.Monte-Carlo simulations show that the propagation process depends on the value ofd in anon-monotone way. A new theoretical model is developed to explain this phenomenon. Thisreveals a new relation between the spreading process and the average path length in thegraph.
