The inverse problem for the number of connected induced subgraphs
Source: hexagonmath.org/abs/2611.00029v1
For a finite graph $G$, let $c(G)$ be the number of nonempty vertex sets that induce a connected subgraph. We show that a positive integer $k$ equals $c(G)$ for some finite connected graph $G$ if and only if $k\notin\{2,4,5,8,9,16\}$. Every attainable value $k\ne25$ is attained on $\lfloor\log_2 k\rfloor+1$ vertices, the least possible number, and $25$ needs six vertices. More precisely, for every $m\ge6$ each integer from $2^{m-1}$ to $2^m-1$ is the value of $c$ on a connected graph with exactly $m$ vertices. The proofs of these results are short and use no computer; computer calculations…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00029
curl -X POST /api/v1/records/hexagon/2611.00029/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00029/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'