Name
Abstract | ||
|---|---|---|
We say that a first order formula φ defines a graph G if φ is true on G and false on every grap G' non-isomorphic with G. Let D(G) be the minimum 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 (√nlog n), we prove the bound D(G) = O (√n). This result applies to planar graphs and, more generally, to graphs of bounded genus.Our proof techniques are based on the characterization of the quantifier rank as the length of the Ehrenfeucht game on non-isomorphic graphs. We use the separator theorems to design a winning strategy for Spoiler in this game. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.tcs.2005.05.003 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
bound D,bounded degree,nlog n,grap G,n denotes,graph G,degree O,order definability,bounded genus,log n,Ehrenfeucht game | Journal | 343 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 6 |
PageRank | References | Authors |
0.54 | 11 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Verbitsky | 1 | 191 | 27.50 |