2003/11/04 by Oleg Pikhurko, Helmut Veith, Pikhurko, Oleg +3
Computer Science · Engineering · #03C13 #05C60 #68Q19 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Graph Labeling and Dimension Problems #Logic (math.LO) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.math/0311041
openalex publication_date 2003/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say that a first order formula A distinguishes a graph G from another graph G' if A is true on G and false on G'. Provided G and G' are non-isomorphic, let D(G,G') denote the minimal quantifier rank of a such formula. We prove that, if G and G' have the same order n, then D(G,G')≤(n+3)/2, which is tight up to an additive constant of 1. The analogous questions are considered for directed graphs (more generally, for arbitrary structures with maximum relation arity 2) and for k-uniform hypergraphs. Also, we study defining formulas, where we require that A distinguishes G from any other non-isomorphic G'.