The topological-surface asymptotic bondage-number conjecture

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 ckc'_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.

Sources & referencesView supporting material

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.