We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Brushing Number and Zero-Forcing Number of Graphs and Their Line Graphs.
- Authors
Erzurumluoğlu, Aras; Meagher, Karen; Pike, David
- Abstract
In this paper we consider one of the most extensively studied graph search parameters, namely the zero-forcing number of a graph. We relate the zero-forcing number to the brushing number, which as a graph parameter gained recent attention due to certain industrial applications where a network system needs to be cleaned efficiently. In particular, we prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Eroh, Kang and Yi conjectured that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph, which we settle in the affirmative. Moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight.
- Subjects
GRAPHIC methods; GRAPH theory; GEOMETRIC vertices; GRAPH connectivity; MATHEMATICAL connectedness
- Publication
Graphs & Combinatorics, 2018, Vol 34, Issue 6, p1279
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-018-1964-y