Bounds on the k-restricted arc connectivity of some bipartite tournaments

C. Balbuena, D. González-Moreno and M. Olsen

Applied Mathematics and Computation, 2018, vol. 331, issue C, 54-60

Abstract: For k ≥ 2, a strongly connected digraph D is called λk′-connected if it contains a set of arcs W such that D−W contains at least k non-trivial strong components. The k-restricted arc connectivity of a digraph D was defined by Volkmann as λk′(D)=min{|W|:Wisak-restrictedarc-cut}. In this paper we bound λk′(T) for a family of bipartite tournaments T called projective bipartite tournaments. We also introduce a family of “good” bipartite oriented digraphs. For a good bipartite tournament T we prove that if the minimum degree of T is at least 1.5k−1 then k(k−1)≤λk′(T)≤k(N−2k−2), where N is the order of the tournament. As a consequence, we derive better bounds for circulant bipartite tournaments.

Keywords: Digraphs; Bipartite; Tournament; Projective plane (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318301486
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:331:y:2018:i:c:p:54-60

DOI: 10.1016/j.amc.2018.02.038

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().