The topological-surface asymptotic bondage-number conjecture

About 14 years old · traced to

Let GG be a connected graph of orientable genus hh and non-orientable genus kk. Let b(G)b(G) be its bondage number and Δ(G)\Delta(G) its maximum vertex degree. Let chc_h and ck′c'_k be constants depending, respectively, on the orientable and non-orientable genera of GG, and let o(h)o(h) and o(k)o(k) denote the genus-dependent terms appearing in the conjecture. Topological-surface bondage-number conjecture.

b(G)≤min⁡{ch, ck′, Δ(G)+o(h), Δ(G)+o(k)}.b(G)\le\min\{c_h,\,c'_k,\,\Delta(G)+o(h),\,\Delta(G)+o(k)\}.

The conjecture proposes that refinements of the paper's surface-embedding arguments yield both constant and maximum-degree-based upper bounds across topological surfaces. The paper presents it as a general conjectural direction after proving explicit bounds, but no resolution is supplied.

References

Primary source

Andrei Gagarin and Vadim Zverovich, “The bondage number of graphs on topological surfaces and Teschner's conjecture”, arXiv:1209.1362 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.