Production matrices for geometric graphs

Clemens Huemer; Carlos Seara; Rodrigo I. Silveira; Alexander Pilz

doi:10.1016/j.endm.2016.09.052

Production matrices for geometric graphs

Clemens Huemer, Carlos Seara, Rodrigo I. Silveira, Alexander Pilz

Research output: Contribution to journal › Article › peer-review

Abstract

We present production matrices for non-crossing geometric graphs on point sets in convex position, which allow us to derive formulas for the numbers of such graphs. Several known identities for Catalan numbers, Ballot numbers, and Fibonacci numbers arise in a natural way, and also new formulas are obtained, such as a formula for the number of non-crossing geometric graphs with root vertex of given degree. The characteristic polynomials of some of these production matrices are also presented. The proofs make use of generating trees and Riordan arrays.

Original language	English
Pages (from-to)	301-306
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	54
DOIs	https://doi.org/10.1016/j.endm.2016.09.052
Publication status	Published - 1 Oct 2016
Externally published	Yes

Keywords

Catalan number
geometric graph
production matrix
Riordan array

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2016.09.052

Cite this

@article{3e67341689a44458b1a8af25c260b9bf,

title = "Production matrices for geometric graphs",

abstract = "We present production matrices for non-crossing geometric graphs on point sets in convex position, which allow us to derive formulas for the numbers of such graphs. Several known identities for Catalan numbers, Ballot numbers, and Fibonacci numbers arise in a natural way, and also new formulas are obtained, such as a formula for the number of non-crossing geometric graphs with root vertex of given degree. The characteristic polynomials of some of these production matrices are also presented. The proofs make use of generating trees and Riordan arrays.",

keywords = "Catalan number, geometric graph, production matrix, Riordan array",

author = "Clemens Huemer and Carlos Seara and Silveira, {Rodrigo I.} and Alexander Pilz",

year = "2016",

month = oct,

day = "1",

doi = "10.1016/j.endm.2016.09.052",

language = "English",

volume = "54",

pages = "301--306",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Production matrices for geometric graphs

AU - Huemer, Clemens

AU - Seara, Carlos

AU - Silveira, Rodrigo I.

AU - Pilz, Alexander

PY - 2016/10/1

Y1 - 2016/10/1

N2 - We present production matrices for non-crossing geometric graphs on point sets in convex position, which allow us to derive formulas for the numbers of such graphs. Several known identities for Catalan numbers, Ballot numbers, and Fibonacci numbers arise in a natural way, and also new formulas are obtained, such as a formula for the number of non-crossing geometric graphs with root vertex of given degree. The characteristic polynomials of some of these production matrices are also presented. The proofs make use of generating trees and Riordan arrays.

AB - We present production matrices for non-crossing geometric graphs on point sets in convex position, which allow us to derive formulas for the numbers of such graphs. Several known identities for Catalan numbers, Ballot numbers, and Fibonacci numbers arise in a natural way, and also new formulas are obtained, such as a formula for the number of non-crossing geometric graphs with root vertex of given degree. The characteristic polynomials of some of these production matrices are also presented. The proofs make use of generating trees and Riordan arrays.

KW - Catalan number

KW - geometric graph

KW - production matrix

KW - Riordan array

UR - http://www.scopus.com/inward/record.url?scp=84992555106&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2016.09.052

DO - 10.1016/j.endm.2016.09.052

M3 - Article

AN - SCOPUS:84992555106

SN - 1571-0653

VL - 54

SP - 301

EP - 306

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Production matrices for geometric graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this