Algorithms and complexity results for finding graphs with extremal Randić index. Issue 4 (15th April 2016)

• Record Type: Journal Article
• Authors: Kincaid, Rex K.; Kunkler, Sarah J.; Lamar, Michael Drew; Phillips, David J.
• Is Part Of: Networks. Volume 67:Issue 4(2016)
• Page Start: 338
• Page End: 347
• Publication Date: 2016-04-15
• Subjects: generalized Randić index; network realization; degree sequence; minimum weight perfect b‐matching; connectivity constraint; synchronization; cortical networks; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21680
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : We show that finding a subgraph realization with the minimum generalized Randić index for a given base graph and degree sequence is solvable in polynomial time by formulating the problem as the minimum weight perfect b ‐matching problem of Edmonds (J Res Natl Bur Stand 69B (1965), 125–130). However, the realization found via this reduction is not guaranteed to be connected. Approximating the minimum weight perfect b ‐matching problem subject to a connectivity constraint is shown to be NP‐hard. For instances in which the optimal solution to the minimum Randić index problem is not connected, we describe a heuristic to connect the graph using pairwise edge exchanges that preserves the degree sequence. Although we focus on finding graph realizations with minimum Randić index, our results extend to finding graph realizations with maximum Randić index as well. Applications of the Randić index are provided to synchronization of neuronal networks controlling respiration in mammals and to normalizing cortical thickness networks in diagnosing individuals with dementia. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 338–347 2016