E-viri
Recenzirano
Odprti dostop
-
Bousquet, Nicolas; Thomassé, Stéphan
Discrete mathematics, 12/2015, Letnik: 338, Številka: 12Journal Article
Let G=(V,E) be a graph. A k-neighborhood in G is a set of vertices consisting of all the vertices at distance at most k from some vertex of G. The hypergraph on vertex set V whose edge set consists of all the k-neighborhoods of G for all k is the neighborhood hypergraph of G. Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension of a graph G as the maximum taken over all induced subgraphs G′ of G of the VC-dimension of the neighborhood hypergraph of G′. For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width. Our motivation is a result of Chepoi et al. (2007) asserting that every planar graph of diameter 2ℓ can be covered by a bounded number of balls of radius ℓ. In fact, they obtained the existence of a function f such that every set F of balls of radius ℓ in a planar graph admits a hitting set of size f(ν) where ν is the maximum number of pairwise disjoint elements of F. Our goal is to generalize the proof of Chepoi et al. (2007) with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the Erdős–Pósa property.
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.