Characteristic polynomials of production matrices for geometric graphs

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

doi:10.1016/j.endm.2017.07.017

Characteristic polynomials of production matrices for geometric graphs

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

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

Abstract

An n×n production matrix for a class of geometric graphs has the property that the numbers of these geometric graphs on up to n vertices can be read off from the powers of the matrix. Recently, we obtained such production matrices for non-crossing geometric graphs on point sets in convex position [Huemer, C., A. Pilz, C. Seara, and R.I. Silveira, Production matrices for geometric graphs, Electronic Notes in Discrete Mathematics 54 (2016) 301–306]. In this note, we determine the characteristic polynomials of these matrices. Then, the Cayley-Hamilton theorem implies relations among the numbers of geometric graphs with different numbers of vertices. Further, relations between characteristic polynomials of production matrices for geometric graphs and Fibonacci numbers are revealed.

Original language	English
Pages (from-to)	631-637
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	61
DOIs	https://doi.org/10.1016/j.endm.2017.07.017
Publication status	Published - 1 Aug 2017
Externally published	Yes

Keywords

Fibonacci number
geometric graph
production matrix
Riordan array

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2017.07.017

Cite this

@article{1d79161a2878499cb037ab6e0a2c68fe,

title = "Characteristic polynomials of production matrices for geometric graphs",

abstract = "An n×n production matrix for a class of geometric graphs has the property that the numbers of these geometric graphs on up to n vertices can be read off from the powers of the matrix. Recently, we obtained such production matrices for non-crossing geometric graphs on point sets in convex position [Huemer, C., A. Pilz, C. Seara, and R.I. Silveira, Production matrices for geometric graphs, Electronic Notes in Discrete Mathematics 54 (2016) 301–306]. In this note, we determine the characteristic polynomials of these matrices. Then, the Cayley-Hamilton theorem implies relations among the numbers of geometric graphs with different numbers of vertices. Further, relations between characteristic polynomials of production matrices for geometric graphs and Fibonacci numbers are revealed.",

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

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

year = "2017",

month = aug,

day = "1",

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

language = "English",

volume = "61",

pages = "631--637",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Characteristic polynomials of production matrices for geometric graphs

AU - Huemer, Clemens

AU - Pilz, Alexander

AU - Seara, Carlos

AU - Silveira, Rodrigo I.

PY - 2017/8/1

Y1 - 2017/8/1

N2 - An n×n production matrix for a class of geometric graphs has the property that the numbers of these geometric graphs on up to n vertices can be read off from the powers of the matrix. Recently, we obtained such production matrices for non-crossing geometric graphs on point sets in convex position [Huemer, C., A. Pilz, C. Seara, and R.I. Silveira, Production matrices for geometric graphs, Electronic Notes in Discrete Mathematics 54 (2016) 301–306]. In this note, we determine the characteristic polynomials of these matrices. Then, the Cayley-Hamilton theorem implies relations among the numbers of geometric graphs with different numbers of vertices. Further, relations between characteristic polynomials of production matrices for geometric graphs and Fibonacci numbers are revealed.

AB - An n×n production matrix for a class of geometric graphs has the property that the numbers of these geometric graphs on up to n vertices can be read off from the powers of the matrix. Recently, we obtained such production matrices for non-crossing geometric graphs on point sets in convex position [Huemer, C., A. Pilz, C. Seara, and R.I. Silveira, Production matrices for geometric graphs, Electronic Notes in Discrete Mathematics 54 (2016) 301–306]. In this note, we determine the characteristic polynomials of these matrices. Then, the Cayley-Hamilton theorem implies relations among the numbers of geometric graphs with different numbers of vertices. Further, relations between characteristic polynomials of production matrices for geometric graphs and Fibonacci numbers are revealed.

KW - Fibonacci number

KW - geometric graph

KW - production matrix

KW - Riordan array

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

U2 - 10.1016/j.endm.2017.07.017

DO - 10.1016/j.endm.2017.07.017

M3 - Article

AN - SCOPUS:85026744017

SN - 1571-0653

VL - 61

SP - 631

EP - 637

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Characteristic polynomials of production matrices for geometric graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this