4 papers
On the -anti-traceability Conjecture
Bin Chen, Stefanie Gerke, Gregory Gutin +3
An oriented graph is called -anti-traceable if the subdigraph induced by every subset with vertices has a hamiltonian anti-directed path. In this paper, we consider an anti-…
Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
Stefanie Gerke, Gregory Gutin, Anders Yeo +1
A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of ed…
Bounds on Maximum Weight Directed Cut
Jiangdong Ai, Stefanie Gerke, Gregory Gutin +2
We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses.…
Results on the Small Quasi-Kernel Conjecture
Jiangdong Ai, Stefanie Gerke, Gregory Gutin +2
A {\em quasi-kernel} of a digraph is an independent set such that for every vertex , there exists a directed path with one or two arcs…