Kavirathne, Sulani Dinya (2024) Brushing directed graphs. Masters thesis, Memorial University of Newfoundland.
![[img]](https://research.library.mun.ca/style/images/fileicons/application_pdf.png) |
[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. Download (508kB) |
Abstract
Brushing of graphs is an edge searching strategy where the searching agents are called brushes. We focus on brushing directed graphs based on a new model that we have developed. The fundamentals of this model have been influenced by previous studies about brushing undirected graphs. We discuss strategies to brush directed graphs as well as values and bounds for the brushing number of directed graphs. As the main results we give an upper bound for the brushing number of directed acyclic graphs. We also establish exact values for the brushing number of transitive tournaments, complete directed graphs and rotational tournaments. The behaviour of the brushing number of several other types of directed graphs are also taken into consideration.
| Item Type: | Thesis (Masters) |
|---|---|
| URI: | http://research.library.mun.ca/id/eprint/16638 |
| Item ID: | 16638 |
| Additional Information: | Includes bibliographical references (pages 50-51) |
| Keywords: | brushes, brushing number, cleaning, directed graphs, tournaments |
| Department(s): | Science, Faculty of > Mathematics and Statistics |
| Date: | August 2024 |
| Date Type: | Submission |
| Library of Congress Subject Heading: | Directed graphs--Mathematical models; Combinatorial analysis; Graph coloring; Graph algorithms; Discrete mathematics |
Actions (login required)
 |
View Item |
Download statistics
Download statistics