Weighted Counting Formula and $2n/21$ Lower Bound for Induced Subgraphs with Prescribed Degree Parities
Let $G=(V,E)$ be a finite simple graph of order $n\geq 1$, and let $\ell:V\to\{0,1\}$ be a prescribed parity labeling. A set $S\subseteq V$ is called $\ell$-admissible if $d_S(v)\equiv \ell(v)\pmod 2$ for every $v\in S$, where $d_S(v)=|N_G(v)\cap S|$. Let $h_\ell(G)$ be the maximum order of an $\ell$-admissible set and let $f_{\rm oe}(G)=\min_\ell h_\ell(G)$. For $x\in\mathbb R$, define the weighted counting polynomial $$ M_{\ell,x}(G)=\sum_{S\in {\cal A}_\ell(G)}x^{|S|}, $$ where ${\cal A}_\ell(G)$ is the collection of all $\ell$-admissible sets in $G$. For $R\subseteq V$, let $z_\ell(R)$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.16424
curl -X POST /api/v1/records/arxiv/2607.16424/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.16424/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'