Feedback edge set in bipartite digraph

Abstract

Let β(G) denote the minimum size of a feedback edge set of a digraph G, and let γ(G) denote the number of unordered pairs of nonadjacent vertices. Motivated by the Chudnovsky--Seymour--Sullivan conjecture for 3-free digraphs, we study the corresponding feedback-edge problem for bipartite digraphs. In the bipartite setting, γ(G) is taken to count only nonadjacent pairs with ends in distinct partite sets. We prove that every 4-free bipartite digraph G satisfies β(G)≤ γ(G)/2. We also determine the exact Turán number of 2k-free strong bipartite digraphs with partite sets X and Y: if |X|,|Y|≥ k+1, then the maximum number of edges is (|X|−(k−1))(|Y|−(k−1))+2k−2. Finally, for the extremal case k=2, we analyze the structure of 4-free strong bipartite Turán digraphs and prove the sharper bound β(G)≤ γ(G)/3 for all such digraphs. This constant is attained by a natural balanced three-block construction.

Negative edge correlation in complete bipartite graphs
Ying Cao, Houshan Fu
arXiv27 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Almost Gorenstein edge rings of bipartite graphs and their h-vectors
Yuta Hatasa, Koji Matsushita
arXiv1 Nov 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Near-bipartite bricks in which every b-invariant edge is a forcing edge
Yaxian Zhang, Fuliang Lu
arXiv12 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A palindromicity criterion for the h-polynomials of bipartite edge rings
Yuta Hatasa
arXiv2 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Binomial edge ideals of bipartite complements of even cycles
Shahnawaz Ahmad Rather, S. Pirzada, M. Aijaz
arXiv26 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{chen2026feedback,
  title = {{Feedback edge set in bipartite digraph}},
  author = {Bin Chen and Jianfeng Hou and Siyue Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.06462},
  eprint = {2609.06462},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.06462},
}

RIS

TY  - UNPB
TI  - Feedback edge set in bipartite digraph
AU  - Bin Chen
AU  - Jianfeng Hou
AU  - Siyue Liu
PY  - 2026
DA  - 2026/09/06
PB  - arXiv
DO  - 10.48550/arxiv.2609.06462
UR  - https://arxiv.org/abs/2609.06462
AB  - Let β(G) denote the minimum size of a feedback edge set of a digraph G, and let γ(G) denote the number of unordered pairs of nonadjacent vertices. Motivated by the Chudnovsky--Seymour--Sullivan conjecture for 3-free digraphs, we study the corresponding feedback-edge problem for bipartite digraphs. In the bipartite setting, γ(G) is taken to count only nonadjacent pairs with ends in distinct partite sets. We prove that every 4-free bipartite digraph G satisfies β(G)≤ γ(G)/2. We also determine the exact Turán number of 2k-free strong bipartite digraphs with partite sets X and Y: if |X|,|Y|≥ k+1, then the maximum number of edges is (|X|−(k−1))(|Y|−(k−1))+2k−2. Finally, for the extremal case k=2, we analyze the structure of 4-free strong bipartite Turán digraphs and prove the sharper bound β(G)≤ γ(G)/3 for all such digraphs. This constant is attained by a natural balanced three-block construction.
ER  -

Abstract

Related

Cite