Brushing number and zero-forcing number of graphs and their line graphs

DOI10.1007/S00373-018-1964-YzbMATH Open1404.05207arXiv1609.05854OpenAlexW3104253731MaRDI QIDQ1756097FDOQ1756097

Authors: Aras Erzurumluoğlu, K. Meagher, David A. Pike 

Publication date: 11 January 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: In this paper we compare the brushing number of a graph with the zero-forcing number of its line graph. 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. Using a similar construction, we also prove the conjecture that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph; 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.

Full work available at URL: https://arxiv.org/abs/1609.05854

Recommendations

• Forcing brushes
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• On the relationship between the zero forcing number and path cover number for some graphs
• Line graphs: their maximum nullities and zero forcing numbers.
• Some bounds on the zero forcing number of a graph

zbMATH Keywords

line graphbrushing numberzero-forcing number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• Brushing without capacity restrictions
• Game brush number
• Cleaning random graphs with brushes
• Cleaning regular graphs with brushes
• Cleaning a network with brushes
• Clean the graph before you draw it!
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• On minimum rank and zero forcing sets of a graph
• Zero forcing parameters and minimum rank problems
• Some bounds on the zero forcing number of a graph
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• On the complexity of the positive semidefinite zero forcing number
• Fast-mixed searching and related problems on graphs
• Brush your trees!
• Zero forcing number, Grundy domination number, and their variants
• Grundy dominating sequences and zero forcing sets
• Critical ideals, minimum rank and zero forcing number
• Compressed cliques graphs, clique coverings and positive zero forcing
• Line graphs: their maximum nullities and zero forcing numbers.

Cited In (1)

• Forcing brushes

This page was built for publication: Brushing number and zero-forcing number of graphs and their line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756097)