Riordan graphs I: Structural properties
Copyright policy )Riordan graphs I: Structural properties
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 families 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.
45 pages, 12 figures
QA75, Eulerian and Hamiltonian graphs, Pascal graph, Graphs and linear algebra (matrices, eigenvalues, etc.), Exact enumeration problems, generating functions, 004, 510, fractal, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Electronic computers. Computer science, Toeplitz graph, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), Riordan graph, graph decomposition, 05C75, 05A15, 05C45, Riordan matrix
QA75, Eulerian and Hamiltonian graphs, Pascal graph, Graphs and linear algebra (matrices, eigenvalues, etc.), Exact enumeration problems, generating functions, 004, 510, fractal, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Electronic computers. Computer science, Toeplitz graph, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), Riordan graph, graph decomposition, 05C75, 05A15, 05C45, Riordan matrix
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).8 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!