2004/01/26 by Oleg Verbitsky, Verbitsky, Oleg
Computer Science · Mathematics · #03C13 #05C60 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #math.CO #math.LO #msc:03C13 #msc:05C60 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0401361
17 pages
arxiv created 2004/01/26 · openalex publication_date 2004/01/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say that a first order formula Φ defines a graph G if Φ is true on G and false on every graph G' non-isomorphic with G. Let D(G) be the minimal quantifier rank of a such formula. We prove that, if G is a tree of bounded degree or a Hamiltonian (equivalently, 2-connected) outerplanar graph, then D(G)=O(log n), where n denotes the order of G. This bound is optimal up to a constant factor. If h is a constant, for connected graphs with no minor Kh and degree O(√ n/log n), we prove the bound D(G)=O(√ n). This result applies to planar graphs and, more generally, to graphs of bounded genus.