Non-Recursively Constructible Recursive Families of Graphs

  • Colleen Bouey
  • Christina Graves
  • Aaron Ostrander
  • Gregory Palma
Keywords: Tutte polynomial

Abstract

In a publication by Noy and Ribó, 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.

Author Biographies

Colleen Bouey, Loyola Marymount College
Christina Graves, The University of Texas at Tyler

Departement of Mathematics

Assistant Professor

Published
2012-04-16
Article Number
P9