pith. sign in

arxiv: 2507.10826 · v1 · pith:4EN6MQE7new · submitted 2025-07-14 · 🧮 math.CO

On the forts and related parameters of the hypercube graph

classification 🧮 math.CO
keywords numberforcingfortszerohypercubegraphsetsbounds
0
0 comments X
read the original abstract

In 2018, forts were defined as non-empty subsets of vertices in a graph where no vertex outside the set has exactly one neighbor in the set. Forts have since been used to characterize zero forcing sets, model zero forcing as an integer program, and provide lower bounds on the zero forcing number. In this article, we give a complete characterization of minimum forts in the hypercube graph, showing that they are automorphic to one of two sets. In contrast, non-automorphic minimum zero forcing sets are identified with distinct propagation times. We also derive the fractional zero forcing number and bounds on the fort number of the hypercube. When the hypercube's dimension is a power of two, the fort number and fractional zero forcing number are equal to the domination number, total domination number, and open packing number. Lastly, we present general constructions for minimal forts in the Cartesian product of graphs, reflecting some minimal forts of the hypercube.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Spectral bounds for distance coloring and packing parameters of graphs via semidefinite programming

    math.CO 2026-06 unverdicted novelty 4.0

    Spectral and SDP methods yield sharp bounds on injective chromatic number, open packing number, and related parameters, with new exact values for hypercubes.