Weighted Padovan graphs

Iršič Chenoweth, Vesna (author), Klavžar, Sandi (author), Rus, Gregor (author), Tan, Elif (author)

Weighted Padovan graphs $\Phi^{n}_{k}$, $n \geq 1$, $\lfloor \frac{n}{2} \rfloor \leq k \leq \lfloor \frac{2n-2}{3} \rfloor$, are introduced as the graphs whose vertices are all Padovan words of length $n$ with $k$ $1$s, two vertices being adjacent if one can be obtained from the other by replacing exactly one $01$ with a $10$. By definition, $\sum_k |V(\Phi^{n}_{k})|=P_{n+2}$, where $P_n$ is the $n$th 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.

• Language: English
• Keywords: Padovan sequence, weighted Padovan graph, integer partition, median graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 12 str.
• Numbering: Vol. 348, iss. 7, art. 114457
• PID: 20.500.12556/RUL-167807
• UDC: 519.17
• ISSN on article: 0012-365X
• DOI: 10.1016/j.disc.2025.114457
• COBISS.SI-ID: 227687939
• Publication date in RUL: 13.03.2025

Record is a part of a journal

• Title: Discrete mathematics
• Shortened title: Discrete math.
• Publisher: Elsevier
• ISSN: 0012-365X
• COBISS.SI-ID: 1118479

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: Padovanovo zaporedje, uteženi Padovanov graf, particije, medianski grafi