Minimax properties of some density measures in graphs and digraphs. Issue 1 (2nd January 2018)

• Record Type: Journal Article
• Authors: Anderson, Janet; Lai, Hong-Jian; Li, Xiaomin; Lin, Xiaoxia; Xu, Murong
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 1(2018)
• Page Start: 1
• Page End: 12
• Publication Date: 2018-01-02
• Subjects: Minimax theorems -- maximum subdigraph arc-strong connectivity -- maximum subdigraph out-degree -- slicing -- restricted edge-connectivity; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2017.1410498
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: For a graph G, let denote the connectivity, or the edge-connectivity, or the minimum degree of G, and define is a subgraph of . Matula in [ K-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972), pp. 459–480] proved two minimax theorems related to and, and obtained polynomial algorithms to determine, and . The restricted edge-connectivity of G, denoted by, is the minimum size of a restricted edge-cut of G . We define . For a digraph D, let, , and denote the strong connectivity, arc-strong connectivity, minimum in-degree and out-degree of D, respectively. For each, define is a subdigraph of . In this paper, we obtain analogous minmax duality results, which are applied to yield polynomial algorithms to determine, , and for a digraph D and for a graph G .