New bounds for search numbers using probabilistic and algorithmic techniques

Tavakoli, Yashar (2012) New bounds for search numbers using probabilistic and algorithmic techniques. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (21MB) [English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. (Original Version)

Abstract

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.

Actions (login required)

View Item