Some New Graph Interpretations of Padovan Numbers

Padovan numbers and Perrin numbers belong to the family of numbers of the Fibonacci type and they are well described in the literature. In this paper, by studying independent (1,2)-dominating sets in paths and cycles, we obtain new binomial formulas for Padovan and Perrin numbers. As a consequence of graph interpretation, we propose a new dependence between Padovan and Perrin numbers. By studying special independent (1,2)-dominating sets in a composition of two graphs, we define Padovan polynomials of graphs. By the fact that every independent (1,2)-dominating set includes the set of leaves as a subset, in some cases a symmetric structure of the independent (1,2)-dominating set can be used.