New bounds for search numbers using probabilistic and algorithmic techniques
Yashar Tavakoli · Memorial University Research Repository (Memorial University) · 2012
Graph searching is a well-studied subject in graph theory. This thesis concentrates on the magnitude of two different search numbers. First, a new upper bound on the fast search number of a general graph is given. The new result improves the existing bound on the fast search number which is given by the brush number. Based on the improved result, an upper bound for almost all graphs is obtained. Next, using an existing lower bound on the fast search number, a lower bound on the fast search number of almost all graphs is derived. Finally, the only existing upper bound on the node search number of a general graph is improved.