4 papers · 1 filter
Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
Gregory Gutin, Hui Lei, Anders Yeo +1
An oriented multigraph is a directed multigraph without directed 2-cycles. Let denote the minimum size of a feedback arc set in an oriented multigraph . The degre…
Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
Jiangdong Ai, Gregory Gutin, Hui Lei +2
An oriented graph is converse invariant if, for any tournament , the number of copies of in is equal to that of its converse . El Sahili and Ghazo Hanna [J. Grap…
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…