Matching, path covers, and total forcing sets

DOI10.2989/16073606.2018.1542525MaRDI QIDQ5215393zbMATH OpenOpenAlexWikidataFDO

Authors Randy Davila, Michael A. Henning

Publication date 10 February 2020

Published in Quaestiones Mathematicae (Search for Journal in Brave)

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

zbMATH Keywords

matchingpath covertotal forcing set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A dynamic coloring of the vertices of a graph $G$ starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. If the initial set $S$ has the added property that it induces a subgraph of $G$ without isolated vertices, then $S$ is called a total forcing set in $G$. The minimum cardinality of a total forcing set in $G$ is its total forcing number, denoted $F_t(G)$. The path cover number of $G$, denoted $pc(G)$, is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover, while the matching number of $G$, denoted $alph{a}^{\prime }(T)$, is the number of edges in a maximum matching of $G$. Let $T$ be a tree of order at least two. We observe that $pc(T)+1le{F}_t(T)le2pc(T)$, and we prove that $F_t(T)lealph{a}^{\prime }(T)+pc(T)$. Further, we characterize the extremal trees achieving equality in these bounds.

Recommendations

• Total forcing sets and zero forcing sets in trees
• Total forcing and zero forcing in claw-free cubic graphs
• On trees and unicyclic graphs with equal forcing-type numbers
• On the total forcing number of a graph
• Note on forcing problem of trees

Cites work

• Bounds for the Zero Forcing Number of Graphs with Large Girth
• Complexity and computation of connected zero forcing
• Extremal values and bounds for the zero forcing number
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• scientific article; zbMATH DE number 5237312 (Why is no real title available?)
• Matching theory
• Matchings, path covers and domination
• Minimum rank problems
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Proof of a conjecture on the zero forcing number of a graph
• Propagation time for zero forcing on a graph
• Some bounds on the zero forcing number of a graph
• The forcing number of graphs with given girth
• Total domination in graphs
• Upper bounds on the \(k\)-forcing number of a graph
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero forcing sets and the minimum rank of graphs

Cited in

(3)

• Total forcing sets and zero forcing sets in trees
• Bounding the total forcing number of graphs
• An approximation algorithm for zero forcing

This page was built for publication: Matching, path covers, and total forcing sets

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