On Approximating the $d$-Girth of a Graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

On Approximating the $d$-Girth of a Graph


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.
Fichier principal
Vignette du fichier
ark__67375_HCB-TK1GKBGL-Q.pdf (312.03 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

lirmm-00736705 , version 1 (14-09-2019)



David Peleg, Ignasi Sau, 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⟩
118 View
123 Download



Gmail Mastodon Facebook X LinkedIn More