Well-Forced Graphs

Document Type

Article

Publication Date

12-2024

Published In

Graphs And Combinatorics

Abstract

A graph in which all minimal zero forcing sets are in fact minimum zero forcing sets is called a well-forced graph. The main result of this paper is to characterize well-forced trees and based on this characterization present an algorithm for determining which trees are well-forced. As part of this characterization, certain subgraphs are identified as being forbidden in a well-forced graph. Additionally it is shown whether some common families of graphs are well-forced or not. Understanding well-forced graphs turns out to be closely related to the question of which vertices of a graph are in a minimal zero forcing set. A vertex of G that is in no minimal zero forcing set of G is called an irrelevant vertex. For any graph, a sufficient condition for a vertex to be irrelevant is established. In addition, it is proved that this condition is a characterization of irrelevant vertices in trees.

Keywords

Well-forced, Zero forcing, Trees, Irrelevant vertices

Comments

This work is freely available courtesy of Springer Nature's SharedIt content-sharing initiative.

Link to Full Text

Share

COinS