The arXiv preprint examines finite, simple, undirected graphs and graph products, which build a new graph from two existing ones under different rules. An isolation number is a graph parameter for controlling the presence of a specified subgraph; its F-version applies the question to a chosen graph family F. The paper gives deterministic upper and lower bounds across four product types and identifies cases where the value can be stated exactly. Its analysis uses isolation graphs and F-transversals to derive those results.
Direct products yield a two-sided picture
Direct products provide the clearest two-sided picture. For products whose factors have no isolated vertices, the generalized isolation number for a complete multipartite target is bounded above by the smaller of two asymmetric quantities: the isolation number in one factor multiplied by the other factor’s total domination number, or the same calculation with the factors swapped. In the paper’s notation, the bound is min{ι(G,K_d)γ_t(H), ι(H,K_d)γ_t(G)}.
The lower side requires more structure. The result applies when a maximum open packing in one factor induces a matching. Under that condition, the bound includes half the open-packing number of G and the ceiling of twice the number of edges in H divided by the square of H’s maximum degree. The result therefore ties the product’s lower bound to both spacing and degree structure in its factors.
A standout exact case comes from the direct product of a path and an odd cycle. For P_{4ℓ} × C_{2k+1}, the isolation number is exactly ℓ(k+1): the path has order 4ℓ and the cycle has order 2k+1. This turns the general product question into a closed expression for a whole graph family.
Strong products trade packing for isolation
For strong products, the paper gives a general lower bound for the F-isolation number: max{ρ2(G)ι(H,F), ρ2(H)ι(G,F)}. In plain language, the larger of two cross-products sets the floor, pairing a factor’s 2-packing number, a measure of vertex spacing, with the other factor’s F-isolation number. The lower bound is sharp for any F.
The corresponding upper result uses the two factors’ isolation numbers and correction terms for vertices left undominated by minimum isolating sets. That upper bound is sharp as well. Together, the strong-product results show how packing parameters can force a lower limit while domination-related remainders help quantify an upper limit.
Lexicographic products simplify in special cases
Lexicographic products produce a different kind of simplification. When the second factor has zero isolation number for a complete-graph target, the paper gives ι(G ◦ H,K_n)=ι(G,K_r), with r=ceil(n/ω(H)). Here ω(H) is the clique number of H, so the second factor changes the target order through the size of its largest complete subgraph.
Two further exact formulas divide the problem by the second factor’s F-isolation number. When that number is one, the value is γ(G); when it is at least two, the value is γ_t(G), under the connectedness assumptions attached to those results. The split shows why the same product operation can be governed by ordinary domination in one regime and total domination in another.
Cartesian products tie the result to color and size
The Cartesian-product results combine different kinds of structure. One upper bound takes the minimum of two asymmetric expressions, using α_k and α_ℓ, the relevant orders of colorable induced subgraphs, together with an F-isolation number from one factor and a domination number from the other. The estimate is therefore sensitive both to the colorable structure of the factors and to their domination parameters.
For a concrete family, the F-isolation number of a cycle Cartesian-product complete graph is exactly the cycle order: ι(C_m □ K_n,F)=m when m is at least three and n is at least r+3, where r is the largest order among the graphs in F. The simple formula applies only after the complete factor clears that stated size threshold.
The paper also gives two general tools for Cartesian products. If every graph in F is S-prime, an upper bound is the product of the minimum dominating F-transversal sizes of G and H. A separate lower bound is max{ρ2(G)ι(H,F), ρ2(H)ι(G,F)}, again using the larger of two cross-products involving 2-packing and F-isolation parameters.
One hypercube equality remains out of reach
The concluding hypercube result is deliberately unfinished. When k<n, it proves ι(Q_n,Q_k) ≥ γ(Q_{n−k}). The reverse inequality, and therefore the equality that would identify the exact value, remains open. The section supplies a lower bound rather than a completed formula for these products.
The manuscript is identified in its supplied front matter as an arXiv version-one preprint. Its results are conditional mathematical statements: each bound is tied to the product, target graph or structural assumptions specified with it. The unresolved hypercube direction marks a clear limit to what the preprint establishes so far.
Paper data and sources
Original title: On the isolation numbers in graph products
Authors: Boštjan Brešar, Douglas F. Rall
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text