New production matrices for geometric graphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jan 2022Embargo end date: 01 Jan 2020 Spain English Publisher:Elsevier BVJournal:Linear Algebra and its Applications, volume 633, pages 244-280 (issn: 0024-3795,

Copyright policy )Funded by:EC | CONNECT

Authors: Esteban Pascual, Guillermo; Huemer, Clemens; Silveira, Rodrigo Ignacio;

doi: 10.1016/j.laa.2021.10.013 , 10.48550/arxiv.2003.00524

arXiv: 2003.00524

handle: 2117/360864

New production matrices for geometric graphs

- Summary
- Subjects
- Related research
  (2)
- Metrics

Abstract

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

Country

Spain

Related Organizations

Universitat Politècnica de Catalunya
Spain
Universitat Polite`cnica de Catalunya
Spain
University of Alcalá
Spain
Universitat Polit?cnica de Catalunya
Spain
Carleton University
Canada

Keywords

Computational Geometry (cs.CG), FOS: Computer and information sciences, Exact enumeration problems, generating functions, characteristic polynomials, Riordan Arrays, Enumeration in graph theory, Riordan arrays, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta, Grafs, Graph polynomials, Production matrices, generating functions, FOS: Mathematics, Mathematics - Combinatorics, Teoria de, Grafs, Teoria de, :Matemàtiques i estadística::Matemàtica discreta [Àrees temàtiques de la UPC], Geometric graphs, production matrices, Graph theory, Generating functions, geometric graphs, Computer Science - Computational Geometry, Characteristic polynomials, Structural characterization of families of graphs, Combinatorics (math.CO), Anàlisi combinatòria

2 Research products, page 1 of 1

Flips in Higher Order Delaunay Triangulations
2020IsAmongTopNSimilarDocuments
Matching Random Colored Points with Rectangles
2020IsAmongTopNSimilarDocuments

Impact byBIP!

	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).	1
	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.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average