Decay Stability of Unicyclic Graphs

Decay centrality is a parameter-dependent distance-based centrality measure, and a graph is called decay-stable when the induced ranking of its vertices is independent of the decay parameter. Building on our earlier result that almost all trees are decay-unstable, we study connected unicyclic graphs. We first prove a pendant reduction which replaces the part of the graph outside a fixed pendant tree by a single path while preserving all eccentricities inside the tree. This yields a local sufficient criterion for decay-instability in a tree attached to the unique cycle. In particular, a pendant copy of K1,3 attached to the rest of the graph through one of its leaves forces decay-instability. Combining this local obstruction with the classical enumeration of labelled unicyclic graphs and a pendant-appearance theorem of McDiarmid, we prove that the proportion of decay-stable connected labelled unicyclic graphs tends to zero. Thus almost all connected labelled unicyclic graphs are decay-unstable. We conclude with remarks on possible extensions to cactus graphs.