On the number of connected sets in bounded degree graphs

Kustaa Kangas, Petteri Kaski, Janne H. Korhonen, Mikko Koivisto

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

2 Sitaatiot (Scopus)
474 Lataukset (Pure)

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äiskieliEnglanti
Artikkeli#P4.34
Sivut1-19
JulkaisuElectronic Journal of Combinatorics
Vuosikerta25
Numero4
DOI - pysyväislinkit
TilaJulkaistu - 1 tammik. 2018
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Sormenjälki

Sukella tutkimusaiheisiin 'On the number of connected sets in bounded degree graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä