Name
Abstract | ||
|---|---|---|
In this note, we prove that the cop number of any n-vertex graph G, denoted by ${{c}}({{G}})$, is at most ${{O}}\big({{{n}}\over {{\rm lg}} {{n}}}\big)$. Meyniel conjectured ${{c}}({{G}})={{O}}(\sqrt{{{n}}})$. It appears that the best previously known sublinear upper-bound is due to Frankl, who proved ${{c}}({{G}})\leq ({{1}}+ {{o}}({{1}})){{{n}}{{\rm lg}}{{\rm lg}} {{n}}\over {{\rm lg}} {{n}}}$. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/jgt.v58:1 | Journal of Graph Theory |
Keywords | Field | DocType |
graph | Sublinear function,Graph,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
58 | 1 | 0364-9024 |
Citations | PageRank | References |
9 | 1.02 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Chiniforooshan | 1 | 118 | 16.38 |