Brushing Directed Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912061898883072 |
|---|---|
| author | Howell, Jared Kavirathne, Sulani D. Pike, David A. |
| author_facet | Howell, Jared Kavirathne, Sulani D. Pike, David A. |
| contents | Brushing of graphs is a graph searching process in which the searching agents are called brushes. We focus on brushing directed graphs based on a new model in which the brushes can only travel in the same direction as the orientation of the arcs that they traverse. We discuss strategies to brush directed graphs as well as values and bounds for the brushing number of directed graphs. We determine the brushing number for any transitive tournament, which we use to give an upper bound for the brushing number of directed acyclic graphs in general. We also establish exact values for the brushing numbers of complete directed graphs, rooted trees, and rotational tournaments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04559 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Brushing Directed Graphs Howell, Jared Kavirathne, Sulani D. Pike, David A. Combinatorics 05C20, 05C57 Brushing of graphs is a graph searching process in which the searching agents are called brushes. We focus on brushing directed graphs based on a new model in which the brushes can only travel in the same direction as the orientation of the arcs that they traverse. We discuss strategies to brush directed graphs as well as values and bounds for the brushing number of directed graphs. We determine the brushing number for any transitive tournament, which we use to give an upper bound for the brushing number of directed acyclic graphs in general. We also establish exact values for the brushing numbers of complete directed graphs, rooted trees, and rotational tournaments. |
| title | Brushing Directed Graphs |
| topic | Combinatorics 05C20, 05C57 |
| url | https://arxiv.org/abs/2410.04559 |