Weighted Padovan graphs

Iršič Chenoweth V., Klavžar S., Rus G., TAN E.

Discrete Mathematics, vol.348, no.7, 2025 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 348 Issue: 7
  • Publication Date: 2025
  • Doi Number: 10.1016/j.disc.2025.114457
  • Journal Name: Discrete Mathematics
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Computer & Applied Sciences, MathSciNet, zbMATH
  • Keywords: Integer partition, Median graph, Padovan sequence, Weighted Padovan graph
  • Ankara University Affiliated: Yes

Abstract

Weighted Padovan graphs Φkn, n≥1, ⌊[Formula presented]⌋≤k≤⌊[Formula presented]⌋, are introduced as the graphs whose vertices are all Padovan words of length n with k 1s, two vertices being adjacent if one can be obtained from the other by replacing exactly one 01 with a 10. By definition, ∑k|V(Φkn)|=Pn+2, where Pn is the nth Padovan number. Two families of graphs isomorphic to weighted Padovan graphs are presented. The order, the size, the degree, the diameter, the cube polynomial, and the automorphism group of weighted Padovan graphs are determined. It is also proved that they are median graphs.