## Abstract

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.

Original language | English |
---|---|

Article number | #P4.34 |

Pages (from-to) | 1-19 |

Journal | Electronic Journal of Combinatorics |

Volume | 25 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

MoE publication type | A1 Journal article-refereed |