From the 1 of 13 linked papers with an AI index.
13 papers
The Complexity of Mixed Arc-Disjoint Spanning Subdigraphs with Antistrong Connectivity
Jiangdong Ai, Gregory Gutin, Hui Lei +1
A trail is antidirected if its arcs alternate between forward and backward. A digraph is antistrong if, for every ordered pair of distinct vertices , it contains a…
Weighted Counting Formula and Lower Bound for Induced Subgraphs with Prescribed Degree Parities
Gregory Gutin, Yiming Hao, Yacong Zhou
Let be a finite simple graph of order , and let be a prescribed parity labeling. A set is called -admissible if $d_S(v)\e…
On Seymour's and Sullivan's Second Neighbourhood Conjectures
Jiangdong Ai, Stefanie Gerke, Gregory Gutin +3
The paper investigates Seymour's and Sullivan's second neighbourhood conjectures for directed graphs, giving a condition based on the number of transitive triangles that ensures Su…
Edge-chromatic -critical graphs and Overfull Conjecture for graphs with maximum degree
Chunhui Ge, Gregory Gutin, Xuli Qi
Let be a simple graph with maximum degree and chromatic index . A graph is called edge-chromatic -critical if and for…
Note on the size of a stable matching
Gregory Z. Gutin, Philip R. Neary, Anders Yeo
Consider a one-to-one two-sided matching market with workers on one side and single-position firms on the other, and suppose that the largest individually rational matching contain…
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 -vertex graph without isolated vertices con…