Abstrakti
A set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer’s entropy lemma and a computer search, we show that the number of connected sets in a graph with n vertices and maximum vertex degree d is at most O(1.9351 n ) for d = 3, O(1.9812 n ) for d = 4, and O(1.9940 n ) for d = 5. Dually, we construct infinite families of graphs where the number of connected sets is at least Ω(1.7651 n ) for d = 3, Ω(1.8925 n ) for d = 4, and Ω(1.9375 n ) for d = 5.
| Alkuperäiskieli | Englanti |
|---|---|
| Artikkeli | #P4.34 |
| Sivut | 1-19 |
| Julkaisu | Electronic Journal of Combinatorics |
| Vuosikerta | 25 |
| Numero | 4 |
| DOI - pysyväislinkit | |
| Tila | Julkaistu - 1 tammik. 2018 |
| OKM-julkaisutyyppi | A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä |
Rahoitus
∗A preliminary version of this work was presented at the 40th International Workshop on Graph-Theoretic Concepts in Computer Science [22]. The work was supported by the European Research Council, under Grant 338077, and by the Academy of Finland, under Grant 276864.