BROWSE

Related Scientist

pascalgollin,jochen's photo.

pascalgollin,jochen
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Disjoint dijoins for classes of dicuts in finite and infinite digraphs

Cited 0 time in webofscience Cited 0 time in scopus
162 Viewed 0 Downloaded
Title
Disjoint dijoins for classes of dicuts in finite and infinite digraphs
Author(s)
Jochen Pascal Gollin; Heuer, Karl; Stavropoulos, Konstantinos
Publication Date
2022-10
Journal
Combinatorial Theory, v.2, no.3
Publisher
eScholarship Publishing, University of California
Abstract
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of a set of edges meeting every non-empty dicut equals the maximum number of disjoint dicuts in that digraph. Such sets are called dijoins. Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a directed graph equals the minimum size of a non-empty dicut. We study a modification of this question where we restrict our attention to certain classes of non-empty dicuts, i.e. whether for a class of dicuts of a directed graph the maximum number of disjoint sets of edges meeting every dicut in equals the size of a minimum dicut in . In particular, we verify this questions for nested classes of finite dicuts, for the class of dicuts of minimum size, and for classes of infinite dibonds, and we investigate how this generalised setting relates to a capacitated version of this question.
URI
https://pr.ibs.re.kr/handle/8788114/13252
DOI
10.5070/c62359180
ISSN
2766-1334
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse