Riordan graphs I: structural properties

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

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages89-135
Number of pages47
JournalLinear Algebra and its Applications
Volume579
Early online date30 May 2019
DOIs
Publication statusE-pub ahead of print - 30 May 2019

Fingerprint

Hamiltonians
Computer networks
Fractals
Structural Properties
Structural properties
Decomposition
Graph in graph theory
Graph Invariants
Pascal
Hamiltonian circuit
Decomposition Theorem
Otto Toeplitz
Computer Networks
Spectral Properties
Fractal
Cycle

Keywords

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

Cite this

Cheon, Gi-Sang ; Jung, Ji-Hwan ; Kitaev, Sergey ; Mojallal, Seyed Ahmad. / Riordan graphs I : structural properties. In: Linear Algebra and its Applications. 2019 ; Vol. 579. pp. 89-135.
@article{628e9968bc1a495199328ca1dc62f1a9,
title = "Riordan graphs I: structural properties",
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.",
keywords = "Riordan matrix, graph decomposition, fractal, Toeplitz graph, Pascal graph, Riordan graph",
author = "Gi-Sang Cheon and Ji-Hwan Jung and Sergey Kitaev and Mojallal, {Seyed Ahmad}",
year = "2019",
month = "5",
day = "30",
doi = "10.1016/j.laa.2019.05.033",
language = "English",
volume = "579",
pages = "89--135",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",

}

Riordan graphs I : structural properties. / Cheon, Gi-Sang; Jung, Ji-Hwan; Kitaev, Sergey; Mojallal, Seyed Ahmad.

In: Linear Algebra and its Applications, Vol. 579, 15.10.2019, p. 89-135.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Riordan graphs I

T2 - Linear Algebra and its Applications

AU - Cheon, Gi-Sang

AU - Jung, Ji-Hwan

AU - Kitaev, Sergey

AU - Mojallal, Seyed Ahmad

PY - 2019/5/30

Y1 - 2019/5/30

N2 - 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.

AB - 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.

KW - Riordan matrix

KW - graph decomposition

KW - fractal

KW - Toeplitz graph

KW - Pascal graph

KW - Riordan graph

UR - https://www.sciencedirect.com/journal/linear-algebra-and-its-applications

U2 - 10.1016/j.laa.2019.05.033

DO - 10.1016/j.laa.2019.05.033

M3 - Article

VL - 579

SP - 89

EP - 135

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -