Skip to Main content Skip to Navigation
Conference papers

On Approximating the $d$-Girth of a Graph

Abstract : For a finite, simple, undirected graph G and an integer d ≥ 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted g d (G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdős et al. [13, 14] and Bollobás and Brightwell [7] over 20 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Ignasi Sau <>
Submitted on : Saturday, September 14, 2019 - 8:01:04 PM
Last modification on : Thursday, October 15, 2020 - 2:42:04 PM
Long-term archiving on: : Saturday, February 8, 2020 - 3:42:32 PM


Publisher files allowed on an open archive




David Peleg, Ignasi Sau Valls, Mordechai Shalom. On Approximating the $d$-Girth of a Graph. SOFSEM, Jan 2011, Nový Smokovec, Slovakia. pp.467-481, ⟨10.1007/978-3-642-18381-2_39⟩. ⟨lirmm-00736705⟩



Record views


Files downloads