The First Order Definability of Graphs with Separators via the Ehrenfeucht Game

Details The First Order Definability of Graphs with Separators via the Ehrenfeucht Game The First Order Definability of Graphs with Separators via the Ehrenfeucht Game

2004-01-26

arxiv.org/abs/math/0401361v1

Mathematics

Combinatorics

17 pages

Scientific paper

We say that a first order formula $\Phi$ defines a graph $G$ if $\Phi$ 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 $K_h$ and degree $O(\sqrt n/\log n)$, we prove the bound $D(G)=O(\sqrt n)$. This result applies to planar graphs and, more generally, to graphs of bounded genus.

Affiliated with

Also associated with

No associations

Rating

The First Order Definability of Graphs with Separators via the Ehrenfeucht Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The First Order Definability of Graphs with Separators via the Ehrenfeucht Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The First Order Definability of Graphs with Separators via the Ehrenfeucht Game will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143461