New production matrices for geometric graphs

We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs i...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2022-01, Vol.633, p.244-280
Main Authors: Esteban, Guillermo, Huemer, Clemens, Silveira, Rodrigo I.
Format: Article
Language:English
Subjects:
Characteristic polynomials
Combinatorial analysis
Eigenvectors
Generating functions
Geometric graphs
Graphs
Linear algebra
Polynomials
Production matrices
Riordan Arrays
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2021.10.013