Ya-Cong Zhou

Bounds on Odd and Odd-Even Induced Subgraphs

Qiwen Guo, Gregory Gutin, Yiming Hao +3

Let $G$ be an $n$ -vertex graph and let $ℓ : V (G) \to F_{2}$ prescribe degree parities. A set $S \subseteq V (G)$ is $ℓ$ -admissible if every $v \in S$ has degree congruent to…

The optimal constant for minimum weight feedback arc sets in oriented graphs

Yacong Zhou

Let $D$ be an oriented graph (a digraph with no directed 2-cycles) with maximum degree $Δ \geq 1$ , equipped with nonnegative arc weights of total weight $w (D)$ , and let $\mathrm{fas}…

Weighted Counting Formula and $2 n /21$ Lower Bound for Induced Subgraphs with Prescribed Degree Parities

Gregory Gutin, Yiming Hao, Yacong Zhou

Let $G = (V, E)$ be a finite simple graph of order $n \geq 1$ , and let $ℓ : V \to {0, 1}$ be a prescribed parity labeling. A set $S \subseteq V$ is called $ℓ$ -admissible if $d_S(v)\e…

A discrepancy dichotomy for 1-factorizations of signed complete bipartite graphs

Yisai Xue, Yacong Zhou

Given a signing $σ : E (K_{n, n}) \to {- 1, + 1}$ of the complete bipartite graph, when does $K_{n, n}$ admit a $1$ -factorization in which every perfect matching has discrepancy boun…

Forward Arc Maximization for Hamilton Oriented Cycles and Paths in Generalizations of Tournaments

Q. Guo, G. Gutin, Y. Lan +3

Gishboliner, Krivelevich, and Michaeli (2023) conjectured the following generalization of Dirac's theorem: If the minimum degree $δ$ of an $n$ -vertex oriented graph $G$ is greater…

math.CO2025

Feedback vertex sets of digraphs with bounded maximum degree

Jiangdong Ai, Gregory Gutin, Xiangzhou Liu +2

A digraph $D$ is an oriented graph if $D$ does not have a pair of opposite arcs. The degree of a vertex $v$ of $D$ is the sum of the in-degree and out-degree of $v .$ Let $f v s (D)$ b…

math.CO2025

Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs

Gregory Gutin, Mads Anker Nielsen, Anders Yeo +1

Let $D = (V (D), A (D))$ be a digraph with at least one directed cycle. A set $F$ of arcs is a feedback arc set (FAS) if $D - F$ has no directed cycle. The FAS decomposition number ${\rm…

math.CO2025

Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition

Jiangdong Ai, Qiwen Guo, Gregory Gutin +4

Erd{\H o}s (1963) initiated extensive graph discrepancy research on 2-edge-colored graphs. Gishboliner, Krivelevich, and Michaeli (2023) launched similar research on oriented graph…

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 $fas (D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$ . The degre…

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials

Jiangdong Ai, Gregory Gutin, Hui Lei +2

An oriented graph $D$ is converse invariant if, for any tournament $T$ , the number of copies of $D$ in $T$ is equal to that of its converse $- D$ . El Sahili and Ghazo Hanna [J. Grap…

On the $k$ -anti-traceability Conjecture

Bin Chen, Stefanie Gerke, Gregory Gutin +3

An oriented graph is called $k$ -anti-traceable if the subdigraph induced by every subset with $k$ 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…

Quasi-kernels in split graphs

Hélène Langlois, Frédéric Meunier, Romeo Rizzi +2

In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The ``small quas…

Note on Disjoint Cycles in Multipartite Tournaments

Gregory Gutin, Wei Li, Shujing Wang +2

In 1981, Bermond and Thomassen conjectured that for any positive integer $k$ , every digraph with minimum out-degree at least $2 k - 1$ admits $k$ vertex-disjoint directed cycles. In t…

On Seymour's and Sullivan's Second Neighbourhood Conjectures

Jiangdong Ai, Stefanie Gerke, Gregory Gutin +3

For a vertex $x$ of a digraph, $d^{+} (x)$ ( $d^{-} (x)$ , resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++} (x)$ is the number of vertices at distance 2 from…