Journal
INFORMATION PROCESSING LETTERS
Volume 174, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2021.106194
Keywords
Bondy-Lovasz lemma; Gyori-Lovasz Theorem; Graph diameter; Graph partitioning; Graph algorithms
Categories
Funding
- NSF [CCF-0643934, CCF-0729102]
- Korea Foundation for Advanced Studies
- National Research Foundation of Korea (NRF) - Korea government (MSIT) [NRF-2019R1C1C1008934]
- AFOSR [FA9550-09-1-0100]
- Microsoft Research New Faculty Fellowship
- Google Research Grant
- Alfred P. Sloan Foundation Fellowship
Ask authors/readers for more resources
We present a strengthened version of a lemma by Bondy and Lovasz, which establishes the connectivity of a graph of spanning trees and proves an asymptotically tight bound on the worst-case diameter.
We present a strengthened version of a lemma due to Bondy and Lovasz. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k = 2 case of the Gyori-Lovasz Theorem on partitioning of k-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight O(vertical bar V vertical bar(2)) bound on the worst-case diameter of this graph of spanning trees. (C) 2021 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
