Non-recursively constructible recursive families of graphs

MaRDI QIDQ426873zbMATH OpenFDO

Authors Christina Graves, Aaron Ostrander, Gregory Palma, Colleen Bouey

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Tutte polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

Summary: In a publication by \textit{M. Noy} and \textit{A. Ribó} [Adv. Appl. Math. 32, No. 1--2, 350--363 (2004; Zbl 1041.05050)], it was shown that recursively constructible families of graphs are recursive. The authors also conjecture that the converse holds; that is, recursive families are also recursively constructible. In this paper, we provide two specific counterexamples to this conjecture, which we then extend to an infinite family of counterexamples.

Recommendations

• Recursively constructible families of graphs
• scientific article; zbMATH DE number 4023320
• scientific article; zbMATH DE number 4105024
• Some work towards the proof of the reconstruction conjecture
• A counterexample to the reconstruction conjecture for locally finite trees

Cited in

(2)

• Recursively constructible families of graphs
• Recurrence relations for graph polynomials on bi-iterative families of graphs

This page was built for publication: Non-recursively constructible recursive families of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426873)