Almost all trees are decay-unstable
DOI:
https://doi.org/10.2140/mscand.2026.132.1Keywords:
centrality measure, decay stability, treesAbstract
Decay centrality is a centrality measure that was introduced to address the sensitivity of traditional closeness measures to distant vertices. We prove that almost all trees are not decay stable, confirming a conjecture of Coroničova Hurajová, Gago and Madaras (2018). A construction that generates all decay stable trees is also given.
References
A. Aytaç and Z. N. Odabaş, “Residual closeness of wheels and related networks”, Internat. J. Found. Comput. Sci. 22:5 (2011), 1229–1240. https://doi.org/10.1142/S0129054111008660
F. Bloch, M. O. Jackson, and P. Tebaldi, “Centrality measures in networks”, Soc. Choice Welf. 61:2 (2023), 413–453. https://doi.org/10.1007/s00355-023-01456-4
C. A. Charalambides, Enumerative combinatorics, 1st ed., Chapman & Hall/CRC, Boca Raton, FL, 2002. https://doi.org/10.1201/9781315273112
P. Chebotarev and D. A. Gubanov, “How to choose the most appropriate centrality measure? A decision-tree approach”, IEEE Transactions on Systems, Man, and Cybernetics: Systems 55:3 (2025), 1694–1706. https://doi.org/10.1109/TSMC.2024.3510633
J. Coroničová Hurajová, S. Gago, and T. Madaras, “On decay centrality in graphs”, Math. Scand. 123:1 (2018), 39–50. https://doi.org/10.7146/math.scand.a-106210
C. Dangalchev, “Residual closeness in networks”, Phys. A: Stat. Mech. Appl. 365:2 (2006), 556–564. https://doi.org/10.1016/j.physa.2005.12.020
C. Dangalchev, “Residual closeness and generalized closeness”, Internat. J. Found. Comput. Sci. 22:8 (2011), 1939–1948. https://doi.org/10.1142/S0129054111009136
C. Dangalchev, “Residual closeness of generalized thorn graphs”, Fund. Inform. 162:1 (2018), 1–15. https://doi.org/10.3233/fi-2018-1710
G. H. Hardy and S. Ramanujan, “Asymptotic formulae in combinatory analysis”, Proc. London Math. Soc. (2) 17 (1918), 75–115. https://doi.org/10.1112/plms/s2-17.1.75
M. O. Jackson, Social and economic networks, Princeton Univ. Press, 2008. https://doi.org/10.2307/j.ctvcm4gh1
M. O. Jackson and A. Wolinsky, “A strategic model of social and economic networks”, J. Econom. Theory 71:1 (1996), 44–74. https://doi.org/10.1006/jeth.1996.0108
L. Katz, “A new status index derived from sociometric analysis”, Psychometrika 18:1 (1953), 39–43. https://doi.org/10.1007/BF02289026
V. Latora and M. Marchiori, “Efficient behavior of small-world networks”, Phys. Rev. Lett. 87 (Oct 2001), art. id. 198701. https://doi.org/10.1103/PhysRevLett.87.198701
N. R. Council, Network science, The National Academies Press, Washington, DC, 2005. https://doi.org/10.17226/11516
Z. N. Odabaş and A. Aytaç, “Residual closeness in cycles and related networks”, Fund. Inform. 124:3 (2013), 297–307. https://doi.org/10.3233/fi-2013-835
R. Otter, “The number of trees”, Ann. of Math. (2) 49 (1948), 583–599. https://doi.org/10.2307/1969046
C. Riveros, J. Salas, and O. Skibski, “How do centrality measures choose the root of trees?”, pp. 12:1–12:17 in 26th International Conference on Database Theory, edited by F. Geerts and B. Vandevoort, LIPIcs. Leibniz Int. Proc. Inform. 255, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2023. https://doi.org/10.4230/lipics.icdt.2023.12
D. Rupnik Poklukar and J. Žerovnik, “Generalized closeness and decay stability of some graphs”, Mathematics 13:6 (2025), art. id. 939. https://doi.org/10.3390/math13060939
T. Turaci and V. Aytaç, “Residual closeness of splitting networks”, Ars Combin. 130 (2017), 17–27. https://combinatorialpress.com/ars-articles/volume-130-ars-articles/residual-closeness-of-splitting-networks/
T. Turaci and M. Ökten, “Vulnerability of Mycielski graphs via residual closeness”, Ars Combin. 118 (2015), 419–427. https://combinatorialpress.com/ars-articles/volume-118-ars-articles/vulnerability-of-mycielski-graphs-via-residual-closeness/
Z. Wan, Y. Mahajan, B. W. Kang, T. J. Moore, and J.-H. Cho, “A survey on centrality metrics and their network resilience analysis”, IEEE Access 9 (2021), 104773–104819. https://doi.org/10.1109/ACCESS.2021.3094196
