Riordan graphs I: structural properties

Gi-Sang Cheon, Ji-Hwan Jung, Sergey Kitaev, Seyed Ahmad Mojallal

Research output: Contribution to journalArticle

3 Citations (Scopus)
3 Downloads (Pure)

Abstract

In this paper, we use the theory of Riordan matrices to introduce the notion of a Riordan graph. The Riordan graphs are a far-reaching generalization of the well known and well studied Pascal graphs and Toeplitz graphs, and also some other fami- lies of graphs. The Riordan graphs are proved to have a number of interesting (fractal) properties, which can be useful in creating computer networks with certain desirable features, or in obtaining useful information when designing algorithms to compute values of graph invariants. The main focus in this paper is the study of structural properties of families of Riordan graphs obtained from infinite Riordan graphs, which includes a fundamental decomposition theorem and certain conditions on Riordan graphs to have an Eulerian trail/cycle or a Hamiltonian cycle. We will study spectral properties of the Riordan graphs in a follow up paper.
Original languageEnglish
Pages (from-to)89-135
Number of pages47
JournalLinear Algebra and its Applications
Volume579
Early online date30 May 2019
DOIs
Publication statusPublished - 15 Oct 2019

Keywords

  • Riordan matrix
  • graph decomposition
  • fractal
  • Toeplitz graph
  • Pascal graph
  • Riordan graph

Fingerprint Dive into the research topics of 'Riordan graphs I: structural properties'. Together they form a unique fingerprint.

Cite this