Guoli Ding
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Guoli Ding has a total of 35 co-authors. Here are the top co-authors by number of shared publications:
- Wenan Zang
Department of Mathematics, The University of Hong Kong, Pok Fu Lam, China
5 shared publications - Bogdan Oporowski
Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA
3 shared publications - Jinko Kanno
College of Engineer- ing and Science Louisiana Tech University 71272 Ruston LA USA
3 shared publications - Xujin Chen
Chinese Academy of Sciences
3 shared publications - Emily Marshall
Arcadia University
2 shared publications - Haidong Wu
Department of Mathematics The University of Mississippi University 38677 MS U.S.A
2 shared publications
Latest Publications
- Open Access
Unavoidable immersions of 4- and $f(t)$-edge-connected graphs
In this paper we prove that every sufficiently large 4-edge-connected graph contains the double cycle, $C_{2,r}$, as an immersion. In proving this, we develop a new tool we call a ring-decomposition. We also prove that linear edge-connectivity implies the presence of a $C_{t,r}$ immersion in a sufficiently large graph, where $C_{t,r}$ denotes the graph obtained from a cycle on $r$ vertices by adding $(t-1)$ edges in parallel to each existing edge; this result is an edge-analogue of a result of Böhme, Kawarabayashi, Maharry, and Mojar. We then use the latter result to provide an unavoidable minor theorem for highly connected line graphs.Open AccessUnavoidable immersions of 4- and $f(t)$-edge-connected graphs
In this paper we prove that every sufficiently large 4-edge-connected graph contains the double cycle, $C_{2,r}$, as an immersion. In proving this, we develop a new tool we call a ring-decomposition. We also prove that linear edge-connectivity implies the presence of a $C_{t,r}$ immersion in a sufficiently large graph, where $C_{t,r}$ denotes the graph obtained from a cycle on $r$ vertices by adding $(t-1)$ edges in parallel to each existing edge; this result is an edge-analogue of a result of Böhme, Kawarabayashi, Maharry, and Mojar. We then use the latter result to provide an unavoidable minor theorem for highly connected line graphs. - 23 February 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (1)
Packing Feedback Arc Sets in Tournaments Exactly
- 23 February 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (1)
Packing Feedback Arc Sets in Tournaments Exactly
- Open Access
Unavoidable Induced Subgraph of Infinite 2-connected Graphs
In 1930, Ramsey proved that every infinite graph contains either an infinite clique or an infinite independent set as an induced subgraph. K\"{o}nig proved that every infinite graph contains either a ray or a vertex of infinite degree. In this paper, we establish the 2-connected analog of these results.
Open AccessUnavoidable Induced Subgraph of Infinite 2-connected Graphs
In 1930, Ramsey proved that every infinite graph contains either an infinite clique or an infinite independent set as an induced subgraph. K\"{o}nig proved that every infinite graph contains either a ray or a vertex of infinite degree. In this paper, we establish the 2-connected analog of these results.
- Open Access
Unavoidable Induced Subgraphs of Large 2-Connected Graphs
Ramsey proved that for every positive integer $n$, every sufficiently large graph contains an induced $K_n$ or $\overline{K}_n$. Among the many extensions of Ramsey's Theorem there is an analogue for connected graphs: for every positive integer $n$, every sufficiently large connected graph contains an induced $K_n$, $K_{1,n}$, or $P_n$. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: $K_n$, a subdivision of $K_{2,n}$, a subdivision of $K_{2,n}$ with an edge between the two vertices of degree $n$, and a well-defined structure similar to a ladder.Open AccessUnavoidable Induced Subgraphs of Large 2-Connected Graphs
Ramsey proved that for every positive integer $n$, every sufficiently large graph contains an induced $K_n$ or $\overline{K}_n$. Among the many extensions of Ramsey's Theorem there is an analogue for connected graphs: for every positive integer $n$, every sufficiently large connected graph contains an induced $K_n$, $K_{1,n}$, or $P_n$. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: $K_n$, a subdivision of $K_{2,n}$, a subdivision of $K_{2,n}$ with an edge between the two vertices of degree $n$, and a well-defined structure similar to a ladder. - Open Access
Online MinCut: Competitive and Regret Analysis
In this paper we study the mincut problem in the online setting. We consider two distinct models: A) competitive analysis and B) regret analysis. In the competitive setting we consider the vertex arrival model; whenever a new vertex arrives it's neighborhood with respect to the set of known vertices is revealed. An online algorithm must make an irrevocable decision to determine the side of the cut that the vertex must belong to in order to minimize the size of the final cut. Various models are considered. 1) For classical and advice models we give tight bounds on the competitive ratio of deterministic algorithms. 2) Next we consider few semi-adversarial inputs: random order of arrival with adversarially generated and sparse graphs. 3) Lastly we derive some structural properties of \mc-type problems with respect to greedy strategies. Finally we consider a non-stationary regret setting with a variational budget $V_T$ and give tights bounds on the regret function. Specifically, we show that if $V_T$ is sublinear in $T$ (number of rounds) then there is a deterministic algorithm achieving a sublinear regret bound ($O(V_T)$). Further, this is optimal, even if randomization is allowed.Open AccessOnline MinCut: Competitive and Regret Analysis
In this paper we study the mincut problem in the online setting. We consider two distinct models: A) competitive analysis and B) regret analysis. In the competitive setting we consider the vertex arrival model; whenever a new vertex arrives it's neighborhood with respect to the set of known vertices is revealed. An online algorithm must make an irrevocable decision to determine the side of the cut that the vertex must belong to in order to minimize the size of the final cut. Various models are considered. 1) For classical and advice models we give tight bounds on the competitive ratio of deterministic algorithms. 2) Next we consider few semi-adversarial inputs: random order of arrival with adversarially generated and sparse graphs. 3) Lastly we derive some structural properties of \mc-type problems with respect to greedy strategies. Finally we consider a non-stationary regret setting with a variational budget $V_T$ and give tights bounds on the regret function. Specifically, we show that if $V_T$ is sublinear in $T$ (number of rounds) then there is a deterministic algorithm achieving a sublinear regret bound ($O(V_T)$). Further, this is optimal, even if randomization is allowed. - 14 February 2018
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 34 (2) , 289-312
Minimal k-Connected Non-Hamiltonian Graphs
- 14 February 2018
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 34 (2) , 289-312
Minimal k-Connected Non-Hamiltonian Graphs
- 1 February 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 43 (1) , 64-99
When Is the Matching Polytope Box-Totally Dual Integral?
Let G = (V, E) be a graph. The matching polytope of G, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds [10] [Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69(1–2):125–130.], P(G) is determined by the following linear system π(G): x(e) ≥ 0 for each e ∈ E; x(δ(v)) ≤ 1 for each v ∈ V; and x(E[U]) ≤ ½|U|⌋ for each U ⊆ V with |U| odd. In 1978, Cunningham and Marsh [6] [Cunningham W, Marsh A (1978) A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral combinatorics. Mathematical Programming Studies, Vol. 8 (Springer, Berlin), 50–72.] strengthened this theorem by showing that π(G) is always totally dual integral. In 1984, Edmonds and Giles [11] [Edmonds J, Giles R (1984) Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization (Academic Press, Toronto), 117–129.] initiated the study of graphs G for which π(G) is box-totally dual integral. In this paper, we present a structural characterization of all such graphs, and develop a general and powerful method for establishing box-total dual integrality. The online appendix is available at https://doi.org/10.1287/moor.2017.0852 .
- 1 February 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 43 (1) , 64-99
When Is the Matching Polytope Box-Totally Dual Integral?
Let G = (V, E) be a graph. The matching polytope of G, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds [10] [Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69(1–2):125–130.], P(G) is determined by the following linear system π(G): x(e) ≥ 0 for each e ∈ E; x(δ(v)) ≤ 1 for each v ∈ V; and x(E[U]) ≤ ½|U|⌋ for each U ⊆ V with |U| odd. In 1978, Cunningham and Marsh [6] [Cunningham W, Marsh A (1978) A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral combinatorics. Mathematical Programming Studies, Vol. 8 (Springer, Berlin), 50–72.] strengthened this theorem by showing that π(G) is always totally dual integral. In 1984, Edmonds and Giles [11] [Edmonds J, Giles R (1984) Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization (Academic Press, Toronto), 117–129.] initiated the study of graphs G for which π(G) is box-totally dual integral. In this paper, we present a structural characterization of all such graphs, and develop a general and powerful method for establishing box-total dual integrality. The online appendix is available at https://doi.org/10.1287/moor.2017.0852 .
- Open Access
- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.55
On Almost-Planar Graphs
A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G\backslash e$ and $G/e$ is planar. In 1990, Gubser characterized 3-connected almost-planar graphs in his dissertation. However, his proof is so long that only a small portion of it was published. The main purpose of this paper is to provide a short proof of this result. We also discuss the structure of almost-planar graphs that are not 3-connected.- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.55
Open AccessOn Almost-Planar Graphs
A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G\backslash e$ and $G/e$ is planar. In 1990, Gubser characterized 3-connected almost-planar graphs in his dissertation. However, his proof is so long that only a small portion of it was published. The main purpose of this paper is to provide a short proof of this result. We also discuss the structure of almost-planar graphs that are not 3-connected. - Open Access
- 31 March 2016
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 23 (2) , P2.16
Graphs with no $\bar P_7$-Minor
Let $\bar P_7$ denote the complement of a path on seven vertices. We determine all 4-connected graphs that do not contain $\bar P_7$ as a minor.- 31 March 2016
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 23 (2) , P2.16
Open AccessGraphs with no $\bar P_7$-Minor
Let $\bar P_7$ denote the complement of a path on seven vertices. We determine all 4-connected graphs that do not contain $\bar P_7$ as a minor. - 19 August 2015
- Published by Wiley in Journal of Graph Theory
- Vol. 82 (3) , 253-264
Hall-Type Results for 3-Connected Projective Graphs
- 19 August 2015
- Published by Wiley in Journal of Graph Theory
- Vol. 82 (3) , 253-264
Hall-Type Results for 3-Connected Projective Graphs