Sharp Nordhaus-Gaddum bounds for throttling

Ryan Blair, Gabriel Elvin, Veronika Furst, Leslie Hogben, Tony W. H. Wong · 2026

Read Sharp Nordhaus-Gaddum bounds for throttling by Ryan Blair, Gabriel Elvin, Veronika Furst, Leslie Hogben, Tony W. H. Wong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30950.txt.

Introduction

Ryan Blair, Gabriel Elvin, Veronika Furst, Leslie Hogben and Tony W. H. Wong derive sharp Nordhaus-Gaddum bounds for throttling numbers. Throttling blends two costs of a graph process: the size of the starting set and the time the process takes to finish, combined as a sum or a product. A Nordhaus-Gaddum bound limits a parameter's value on a graph plus, or times, its value on the complement graph, so knowing one side constrains the other. The team treat sum throttling and both variants of product throttling, with and without initial cost.

Four graph processes are covered: standard zero forcing, positive semidefinite forcing, power domination, and the Cops and Robbers game. The bounds obtained are sharp, meaning examples attain them, so no stronger universal limits of this form exist.

Catalog record

CREATORRyan Blair, Gabriel Elvin, Veronika Furst, Leslie Hogben, Tony W. H. Wong
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30950

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sharp Nordhaus-Gaddum bounds for throttling Ryan Blair, Gabriel Elvin, Veronika Furst, Leslie Hogben, Tony W. H. Wong Abstract Throttling is a graph optimization problem, where the throttling number of a graph is the minimum sum or minimum product of the number of vertices in an initial set and the time required to complete a certain graph operation. A Nordhaus-Gaddum bound refers to an upper or lower bound of the sum or product of a graph parameter together with that of its complement. In this paper, we study the Nordhaus-Gaddum sum and product bounds of the various throttling numbers (sum throttling and product throttling with or without initial cost). Graph operations considered are standard zero forcing, positive semidefinite forcing, power domination, and Cops and Robbers. Keywords throttling, Nordhaus-Gaddum, propagation time, zero forcing, positive semidefinite forcing, power domination, Cops and Robbers, graph searching AMS subject classification 05C69, 05C50, 68R10 1 Introduction A Nordhaus-Gaddum (NG) bound is an upper or lower bound on the sum or product of the values of a parameter on a graph and its complement. Aouchiche and Hansen provide an extensive survey of NG bounds in [ 4 ] . By simultaneously limiting the possible values of a graph invariant of G and of its complement \overline{G} , Nordhaus-Gaddum bounds provide useful structural information about a graph, given such information about its complement. In this paper, we focus on the graph parameters known as throttling numbers. Throttling in graphs belongs in the intersection of graph theory and combinatorial optimization. It involves the analysis of the efficiency of a task by minimizing the sum or the product of a measure of the resources used and the time needed to accomplish the task. We consider two metrics: in sum throttling, the total we aim to minimize is the sum of the amount of resources used and the time needed, while product throttling aims to minimize their product. Small differences in the initial set of resources or in the propagation time can have a much larger overall impact on product throttling than they would on sum throttling. Product throttling is separated into two variants, one in which initial cost is taken into account and one in which it is not but at least one time step is required; both stipulations have the effect of ruling out the trivial situation in which the product throttling number of a graph equals 0 . In this paper, we calculate NG sum and product bounds for sum and both types of product throttling for the following four graph parameters: the zero forcing number \operatorname{Z}(G) , the positive semindefinite zero forcing number \operatorname{Z}_{+}(G) , the power domination number \gamma_{P}(G) , and the cop number c(G) of a graph G . Tables 1.1 and 1.2 summarize the NG sum and NG product bounds, respectively. Over all graphs, the NG sum bounds for \operatorname{Z} were known as was the NG sum upper bound for \operatorname{Z}_{+} ; otherwise the results are new. We provide all necessary definitions and some background in the remainder of this section. Section 2 contains our results for standard zero forcing. We construct several novel examples (e.g., Example 2.9 ) used to prove that the new NG bounds we present (e.g., Theorems 2.11 and 2.12 ) are sharp, almost sharp, or tight, even in the subproblem that restricts to graphs for which both G and \overline{G} are connected. In Section 3 we turn our attention to positive semidefinite zero forcing, improving known bounds and establishing new ones. The key findings in this section are Corollaries 3.4 for arbitrary graphs and 3.8 when both G and \overline{G} are connected, with sharpness/tightness provided by several examples. Finally, since both power domination and Cops and Robbers are closely related to graph domination, we consider both of these processes together in Section 4 . The upper and lower bounds in Theorems 4.10 and 4.17 comprise the main results of this section, once again relying on a series of examples to demonstrate sharpness/tightness. 1.1 Notation for graphs and asymptotics A graph is simple, undirected, finite, and has a nonempty vertex set. For a graph G , V(G) denotes the set of vertices and E(G) denotes the set of edges; |V(G)| is the order of G , and an edge between vertices u and v is denoted by uv or vu . The complement of G , denoted by \overline{G} , is the graph (V(G),\overline{E(G)}) where uv\in\overline{E(G)} if and only if uv\notin E(G) for u,v\in V(G) and u\neq v . Any graph whose sets of vertices and edges are subsets of V(G) and E(G) , respectively, is a subgraph of G . Given a set W\subseteq V(G) , the induced subgraph G[W] has V(G[W])=W and E(G[W])=\{uv:uv\in E(G)\mbox{ and }u,v\in W\} . The union of G and G^{\prime} is the graph G\,\cup\,G^{\prime}=(V(G)\cup V^{\prime}(G),E(G)\cup E^{\prime}(G)) . If V(G)\cap V^{\prime}(G)=\emptyset , then the union is disjoint and can be denoted by G\,\dot{\cup}\,G^{\prime} . Two graphs G and G^{\prime} are isomorphic , denoted by G\cong G^{\prime} , if there exists a bijection \varphi:V(G)\to V(G^{\prime}) such that uv\in E(G) if and only if \varphi(u)\varphi(v)\in E(G^{\prime}) . Given v\in V(G) , the (open) neighborhood of v in G is N_{G}(v)=\{u:uv\in E(G)\} , and the closed neighborhood of v in G is N_{G}[v]=N(v)\cup\{v\} , and N_{G}[W]=\cup_{w\in W}N_{G}[W] for W\subseteq V(G) ; if the graph is clear from context, the subscript may be omitted. The degree of a vertex v is \deg_{G}(v)=|N_{G}(v)| . A vertex \ell of a graph G is a leaf if \deg_{G}(\ell)=1 . A vertex u of a graph G is universal if u is adjacent to every other vertex of G . An independent set is a set of vertices of which no two are adjacent. The independence number of G , denoted by \alpha(G) , is the maximum cardinality of an independent set. A path in a graph G is a sequence of distinct vertices v_{1},v_{2},\dots,v_{r} such that for each i with 1\leq i\leq r-1 we have v_{i}v_{i+1}\in E(G) . A graph G is connected if for each pair of vertices u,w\in V(G) there exists a path v_{1},v_{2},\dots,v_{r} with v_{1}=u and v_{r}=w ; a graph is disconnected if it is not connected. The components of G are its maximal connected subgraphs. The path graph P_{n} is the graph with V(P_{n})=\{v_{1},\dots,v_{n}\} and E(P_{n})=\{{v_{i}v_{i+1}}:i=1,\dots,n-1\} . The cycle graph C_{n} is the graph obtained from the path graph P_{n} just described by adding the edge v_{1}v_{n} . The complete graph of order n , which has an edge between every pair of vertices, is denoted by K_{n} . The complete bipartite graph K_{p,q} is the graph with V(K_{p,q})=X\,\dot{\cup}\,Y such that |X|=p and |Y|=q and E(K_{p,q})=\{xy:x\in X\mbox{ and }y\in Y\} ; K_{1,n-1} is called a star . The complete multipartite graph K_{n_{1},\dots,n_{r}} is the graph whose vertices can be partitioned into r parts of sizes n_{1},\ldots,n_{r} and the set of edges is exactly the set of all possible edges between distinct parts. Let f and g be positive real valued functions of n\in\mathbb{N} for n\geq 2 . We say f is o(g) if \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 . We say f is O(g) if there exist positive constants C,k such that f(n)\leq Cg(n) for all n\geq k , and f is \Omega(g)

Read the complete text