Tavakoli, Yashar (2012) New bounds for search numbers using probabilistic and algorithmic techniques. Masters thesis, Memorial University of Newfoundland.
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.
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.
|Item Type:||Thesis (Masters)|
|Additional Information:||Includes bibliographical references (leaves 61-64)|
|Department(s):||Science, Faculty of > Mathematics and Statistics|
|Library of Congress Subject Heading:||Graph theory--Data processing; Mathematics--Graphic methods; Free probability theory; Branch and bound algorithms|
Actions (login required)