A. Yeo

activity

20232025

collaborators

12 papers

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

Odd Induced Subgraphs in Graphs of Maximum Degree Four

Jiangdong Ai, Qiwen Guo, Gregory Gutin +2

A graph is called odd if all of its vertex degrees are odd. A long-standing conjecture asked whether there exists a positive constant $c$ such that every $n$ -vertex graph without i…

math.CO2025

Note on Long Directed Cycles in Eulerian Digraphs

Jiangdong Ai, Gregory Gutin, Fankang He +1

Huang, Ma, Shapira, Sudakov and Yuster (Comb. Prob. Comput. 2013) proved that every Eulerian digraph of average out-degree $d$ has a directed cycle of length at least $d .$ W…

math.CO2025

Large induced subgraphs with prescribed degree parity

Jiangdong Ai, Qiwen Guo, Gregory Gutin +2

A long-standing conjecture of Caro (Discrete Math, 1994), confirmed by Ferber and Krivelevich (Adv Math, 2022), states that every $n$ -vertex graph $G$ without isolated vertices con…

math.CO2025

Judicious Partitions in Edge-Weighted Graphs with Bounded Maximum Weighted Degree

G. Gutin, M. A. Nielsen, A. Yeo +1

In this paper, we investigate bounds for the following judicious $k$ -partitioning problem: Given an edge-weighted graph $G$ , find a $k$ -partition $(V_{1}, V_{2}, \dots, V_{k})$ of $V (G)$ s…

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…

math.CO2024

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…

math.CO2024

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…

math.CO2024

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…

math.CO2023

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…

econ.TH2023

Some coordination problems are harder than others

Argyrios Deligkas, Eduard Eiben, Gregory Gutin +2

In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kin…