\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{booktabs,array}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!50!black,citecolor=blue!50!black,urlcolor=blue!50!black]{hyperref}
\hypersetup{pdftitle={Maximal Independent Sets in Long Graph Subdivisions},pdfauthor={Daniel A. Pyle},pdfsubject={Exact boundary formulas, degree-product asymptotics, and limiting laws},pdfkeywords={maximal independent set, independent domination, graph subdivision, transfer matrix}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\MIS}{\mathcal M}
\newcommand{\Rcal}{\mathcal R}
\newcommand{\kk}{\boldsymbol k}
\newcommand{\EE}{\mathbb E}
\newcommand{\PP}{\mathbb P}
\newcommand{\TV}{d_{\mathrm{TV}}}
\newcommand{\Rea}{\operatorname{Re}}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Bern}{\operatorname{Bern}}
\newcommand{\Normal}{\mathcal N}
\setlength{\emergencystretch}{2em}
\numberwithin{equation}{section}
\title{Maximal Independent Sets in Long Graph Subdivisions}
\author{Daniel A. Pyle\\\small Independent Researcher}
\date{29 October 2026\\\small Research draft for independent review}
\begin{document}
\maketitle
\begin{abstract}
Let $G$ be a finite simple graph, and replace each edge $e$ by a path with $k_e$ new internal vertices. We derive an exact boundary-state formula for the number of maximal independent sets of the resulting graph. If $I=\sum_e k_e$ and $\lambda>1$ satisfies $\lambda^3=\lambda+1$, its leading term is
\[
 \lambda^I(2\lambda+3)^{-|E(G)|}
 \prod_{v\in V(G)}\bigl[\lambda^{2d_v}+(1+\lambda)^{d_v}-1\bigr].
\]
An explicit relative error bound, uniform in the base graph, is at most $\exp(B\sum_e\lambda^{-3k_e/2})-1$, where $B<5.600$. Consequently the leading amplitude depends only on the degree sequence, and the indicators of membership of all original vertices approach an explicit independent Bernoulli law in total variation. These conclusions also hold for growing base graphs under the stated summability condition. For a fixed base graph, we identify the first adjacency-sensitive correction and extend the established one-dimensional Gaussian size law to arbitrary long edge subdivisions. The proofs use standard finite-state transfer methods; the contribution is the explicit assembly at the original vertices and its quantitative consequences.
\end{abstract}
\noindent\textbf{Keywords.} Maximal independent sets; independent domination; graph subdivision; transfer matrix; asymptotic enumeration.\\
\textbf{2020 Mathematics Subject Classification.} 05C69, 05C30, 05C31.

\section{Introduction}
An independent set is \emph{maximal} if no further vertex can be added while preserving independence. This is not the same as having maximum cardinality. A set is maximal independent precisely when every vertex outside it has a neighbor in it; equivalently, it is an independent dominating set.

On a long path, independence and domination impose local constraints that are readily encoded by a small transfer matrix. When many such paths meet at the vertices of a fixed graph, however, their endpoint conditions must be assembled consistently. The purpose of this note is to perform that assembly explicitly. The leading amplitude factors over original vertices, although the exact count generally depends on their adjacency. A positive boundary representation also gives an error estimate that does not hide any dependence on the size or degree of the base graph.

The main result is Theorem~\ref{thm:main}: an explicit degree-product approximation with a universal finite-length relative error. Theorem~\ref{thm:law} gives the corresponding joint law on original vertices, with a dimension-independent total variation estimate. An exact sum over three colors on the edges appears in Theorem~\ref{thm:root}. The later sections extract a first correction for equal subdivision lengths, show that bounded $m\theta^k$ does not suffice for uniform degree-sequence universality, and prove a Gaussian limit for the size of a uniformly chosen maximal independent set when the base graph is fixed.

\subsection{Relation to established enumeration methods}
The one-dimensional recurrence is established prior work. Dod~\cite[Theorems 4.2--4.4]{Dod} gives the weighted path recurrence, exact size coefficients, and a cycle reduction for the independent domination polynomial. Jahari and Alikhani~\cite{JA} develop graph-operation identities and a bivariate path generating function. Three-state cavity recursions for maximal independent sets, exact on trees, appear in Dall'Asta, Pin, and Ramezanpour~\cite[Section V]{DPR}. Transfer matrices and related recursive matrix methods have also been used to enumerate maximal independent sets on grids~\cite{Oh}. More generally, Liu et al.~\cite[Appendix B.1]{Liu} give tensor-network formulations for the independent-set and maximal-independent-set solution spaces.

The bulk growth and size fluctuations in the path case are also known. The blocked one-dimensional configurations studied by Krapivsky and Luck~\cite[Sections 3 and 6]{KL}, with blockade range one, are maximal independent sets of the open chain. Their renewal formulation supplies the corresponding generating function and linear cumulant behavior. Thus the cubic equation, the path recurrence, the finite-state methodology, and the one-dimensional bulk constants are not asserted to be new here.

We specialize these established ideas to simultaneous long edge subdivisions and derive an explicit factorized amplitude, a graph-uniform error bound, and a product approximation for the full set of original-vertex indicators. A targeted literature search did not locate these exact arbitrary-base-graph statements. That search is not an exhaustive priority determination; the results are presented as explicit derivations rather than as a claim of a new transfer-matrix method.\footnote{In particular, the full text of Hu, Mansour, and Song (2017), \href{https://doi.org/10.1216/RMJ-2017-47-7-2219}{doi:10.1216/RMJ-2017-47-7-2219}, was not accessible in this search and has not been inspected. Its theorem-level relationship to this note remains unresolved.}

\section{Definitions and the quantitative main theorem}
Let $G=(V,E)$ be a finite simple graph, with $n=|V|$, $m=|E|$, and degrees $d_v$. Neither connectedness nor a positive minimum degree is assumed. For each $e=uv\in E$, choose an integer $k_e\geq0$ and replace $uv$ by a path from $u$ to $v$ with exactly $k_e$ new internal vertices and $k_e+1$ edges. Distinct replacement paths have disjoint interiors. Write $G_{\kk}$ for the resulting graph, and put
\[
 I=\sum_{e\in E}k_e,\qquad
 M_G(\kk)=|\MIS(G_{\kk})|,
\]
where $\MIS(H)$ is the family of maximal independent sets of $H$. In particular, $|V(G_{\kk})|=n+I$. The vertices in $V$ will be called \emph{original vertices}; this includes original vertices of degree two.

Let $\lambda$ be the positive root of $t^3=t+1$, and define
\begin{align}
 D&=2\lambda+3, & \theta&=\lambda^{-3/2},\label{eq:constants}\\
 A_d&=\lambda^{2d}+(1+\lambda)^d-1
     =\lambda^{2d}+\lambda^{3d}-1, &
 C_G&=D^{-m}\prod_{v\in V}A_{d_v}.\label{eq:amplitude}
\end{align}
Numerically, $\lambda=1.324717957244746\ldots$ and $\theta=0.655865618097142\ldots$. Every $A_d$ is positive; in particular $A_0=1$.

\begin{theorem}[Uniform degree-product estimate]\label{thm:main}
For every finite simple graph $G$ and every vector $\kk$ of nonnegative integers,
\begin{equation}\label{eq:mainbound}
 \left|\frac{M_G(\kk)}{C_G\lambda^I}-1\right|
 \leq \eta_G(\kk)
 :=\prod_{e\in E}(1+B\theta^{k_e})-1
 \leq \exp\!\left(B\sum_{e\in E}\theta^{k_e}\right)-1,
\end{equation}
where the universal constant is
\begin{equation}\label{eq:B}
 B=\frac{2(2\lambda+3)}{\sqrt{9-6\lambda+4/\lambda}}
   =5.599815359286104\ldots.
\end{equation}
Empty products have value one. In particular, an edge-free graph has $M_G(\kk)=C_G=1$ and zero error.
\end{theorem}

The bound is intentionally uniform and can be loose for short replacement paths. It does not require a bound on $n$, $m$, the maximum degree, or the disparity between the lengths. Its proof is given in Section~\ref{sec:proofmain}.

\begin{corollary}[Fixed and growing base graphs]\label{cor:asymptotic}
For a fixed graph $G$ with $m>0$, let $h=\min_e k_e$. As $h\to\infty$,
\begin{equation}\label{eq:fixed}
 M_G(\kk)=C_G\lambda^I\bigl(1+O_G(\theta^h)\bigr).
\end{equation}
More generally, along any sequence of finite simple graphs and subdivision vectors for which
\begin{equation}\label{eq:growing}
 \sum_{e\in E(G)}\theta^{k_e}\longrightarrow0,
\end{equation}
the ratio $M_G(\kk)/(C_G\lambda^I)$ tends to one. A sufficient condition when $m>0$ is $m\theta^h\to0$.
\end{corollary}
\begin{proof}
Use $\sum_e\theta^{k_e}\leq m\theta^h$ and the last bound in~\eqref{eq:mainbound}.
\end{proof}

In particular, two fixed base graphs with the same degree multiset have the same $C_G$. If their subdivision vectors have equal total $I$, and both minimum lengths tend to infinity, their maximal-independent-set counts have ratio tending to one. This forgetfulness of adjacency concerns the leading term, not the exact counts.

\section{An exact boundary formula}\label{sec:boundary}
\subsection{The three states}
At an incidence of an original vertex and an edge, use a two-bit state $(x,a)$: $x$ records selection of the original vertex, and $a$ records selection of its first neighbor along that replacement path. The possible states are
\[
 00,\quad 01,\quad 10,
\]
indexed by $0,1,2$, respectively. State $11$ is forbidden by independence. Let $R$ reverse a pair, so it fixes state $0$ and exchanges states $1$ and $2$.

Along a replacement path, a transition shifts a pair of bits one position to the right. It forbids adjacent ones and the triple $000$. The latter constraint says that an unselected middle vertex must have a selected neighbor. The transition matrix, in the indicated state order, is
\begin{equation}\label{eq:T}
 T=\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}.
\end{equation}
For a path with $k$ internal vertices, define
\begin{equation}\label{eq:K}
 K_k(a,b)=(T^k)_{a,Rb},\qquad a,b\in\{0,1,2\}.
\end{equation}
This is the number of admissible path interiors with the prescribed endpoint states. The $k$ transitions impose domination exactly at the $k$ internal vertices; domination at the original endpoints is not yet imposed. Formula~\eqref{eq:K} also applies when $k=0$: it then enforces consistency of the two descriptions of the original edge.

An incidence assignment is \emph{legal at an original vertex} $v$ if either all its incident states are $10$, or all are in $\{00,01\}$ and at least one is $01$. The first alternative selects $v$; the second leaves it unselected and dominated. An isolated original vertex must be selected and contributes one choice.

\begin{proposition}[Positive boundary contraction]\label{prop:contraction}
The number $M_G(\kk)$ is the sum, over incidence assignments legal at every original vertex, of
\begin{equation}\label{eq:contraction}
 \prod_{e=uv\in E} K_{k_e}(a_{u,e},a_{v,e}).
\end{equation}
All terms in this expression are nonnegative.
\end{proposition}
\begin{proof}
A maximal independent set determines a legal state at every incidence. For fixed states, the choices of interiors on different replacement paths are independent, and their numbers are precisely the factors in~\eqref{eq:contraction}. Conversely, legal incidence states and admissible interiors give an independent set dominating every internal and original vertex. These constructions are inverse, including at $k_e=0$ and at isolated vertices.
\end{proof}

\subsection{Spectral separation and an edge-color sum}
Let $\alpha$ and $\overline\alpha$ be the other two roots of $t^3-t-1$, choosing $\operatorname{Im}\alpha>0$, and set $\Rcal=\{\lambda,\alpha,\overline\alpha\}$. The roots are distinct. For each $r\in\Rcal$, a right eigenvector of $T$ is $(1,r,r^2)^{\mathsf T}$, and a left eigenvector is $(1,r^2,r)$. Their pairing is $1+2r^3=2r+3$. Multiplication by $R$ in~\eqref{eq:K} therefore gives the symmetric formula
\begin{equation}\label{eq:spectralK}
 K_k(a,b)=\sum_{r\in\Rcal}\frac{r^{k+a+b}}{2r+3}.
\end{equation}
This identity holds for every $k\geq0$ and $a,b\in\{0,1,2\}$.

\begin{theorem}[Exact edge-color formula]\label{thm:root}
For every $G$ and $\kk$ as above,
\begin{align}\label{eq:rootformula}
 M_G(\kk)
 &=\sum_{c:E\to\Rcal}
   \left(\prod_{e\in E}\frac{c(e)^{k_e}}{2c(e)+3}\right)
   \prod_{v\in V} F_v(c),\\
 F_v(c)
 &=\prod_{e\ni v}c(e)^2
   +\prod_{e\ni v}(1+c(e))-1.\notag
\end{align}
There are $3^m$ summands, and $F_v(c)=1$ when $d_v=0$.
\end{theorem}
\begin{proof}
Insert~\eqref{eq:spectralK} into Proposition~\ref{prop:contraction} and expand, choosing a root $c(e)$ for each edge. At $v$, selection forces every incident state index to be $2$, giving $\prod_{e\ni v}c(e)^2$. If $v$ is unselected, the allowed indices are $0$ and $1$, but the all-zero choice is excluded. Their sum is $\prod_{e\ni v}(1+c(e))-1$. The factors separate over vertices, proving the formula. At degree zero the unselected contribution vanishes and the selected contribution is one.
\end{proof}

The all-$\lambda$ edge coloring in~\eqref{eq:rootformula} is exactly $C_G\lambda^I$. The remaining colorings describe finite-length interactions through the replacement paths. Formula~\eqref{eq:rootformula} is an exact identity, not a general polynomial-time counting algorithm; its displayed number of terms is exponential in the number of original edges.

\section{The uniform error and the original-vertex law}\label{sec:proofmain}
\subsection{Proof of the relative count estimate}
The cubic root relations give
\[
 \alpha+\overline\alpha=-\lambda,\qquad
 |\alpha|^2=\lambda^{-1},\qquad
 |2\alpha+3|^2=9-6\lambda+4/\lambda.
\]
Define the positive rank-one kernel
\begin{equation}\label{eq:K0}
 K_k^{(0)}(a,b)=\frac{\lambda^{k+a+b}}{D}.
\end{equation}
By~\eqref{eq:spectralK},
\begin{align}\label{eq:entrybound}
 \left|\frac{K_k(a,b)}{K_k^{(0)}(a,b)}-1\right|
 &=\left|2\Rea\!\left[
 \frac{D}{2\alpha+3}\left(\frac\alpha\lambda\right)^{k+a+b}
 \right]\right|\\
 &\leq B\theta^{k+a+b}\leq B\theta^k.\notag
\end{align}
For any complex numbers $\delta_e$ with $|\delta_e|\leq t_e$, expansion of the product gives
\begin{equation}\label{eq:producterror}
 \left|\prod_e(1+\delta_e)-1\right|
 \leq\prod_e(1+t_e)-1.
\end{equation}
Apply this with the entrywise errors in~\eqref{eq:entrybound}, separately to every legal incidence assignment. Its leading product is positive. Thus summing the absolute error over the same legal assignments bounds the total error by $\eta_G(\kk)$ times the contraction with $K^{(0)}$ in place of $K$. The latter contraction is $C_G\lambda^I$, by the vertex factorization in Theorem~\ref{thm:root}. This proves the first inequality of~\eqref{eq:mainbound}. The second follows from $1+x\leq e^x$ for $x\geq0$, completing the proof of Theorem~\ref{thm:main}.

\subsection{Asymptotic independence of all original vertices}
Choose $S$ uniformly from $\MIS(G_{\kk})$, and let $X_v=\mathbf1_{\{v\in S\}}$ for $v\in V$. Define
\begin{equation}\label{eq:pd}
 p_d=\frac{\lambda^{2d}}{A_d},\qquad
 Q_G=\bigotimes_{v\in V}\Bern(p_{d_v}).
\end{equation}
For $d=0$ this is the deterministic value one. The comparison law $Q_G$ is on the original vertices only, not on all vertices of the expanded graph.

\begin{theorem}[Quantitative product law]\label{thm:law}
Let $P_{G,\kk}$ be the joint law of $(X_v)_{v\in V}$. If $\eta_G(\kk)<1$, then
\begin{equation}\label{eq:TV}
 \TV(P_{G,\kk},Q_G)
 \leq\frac{\eta_G(\kk)}{1-\eta_G(\kk)}.
\end{equation}
For an edge-free graph, $P_{G,\kk}=Q_G$ exactly. For a fixed base graph with $m>0$, the joint law converges in total variation to $Q_G$ as $\min_e k_e\to\infty$, with error $O_G(\theta^{\min_e k_e})$. The same approximation holds for a growing sequence of base graphs under~\eqref{eq:growing}.
\end{theorem}
\begin{proof}
For $x\in\{0,1\}^V$, let $W(x)$ count maximal independent sets having original-vertex pattern $x$. Restrict the positive boundary contraction to this pattern. Its rank-one counterpart is
\begin{equation}\label{eq:W0}
 W_0(x)=\lambda^I D^{-m}
 \prod_{v:x_v=1}\lambda^{2d_v}
 \prod_{v:x_v=0}\bigl((1+\lambda)^{d_v}-1\bigr).
\end{equation}
If an isolated vertex has $x_v=0$, then both $W(x)$ and $W_0(x)$ are zero. Otherwise $W_0(x)>0$, and the proof of Theorem~\ref{thm:main}, with the same restricted assignments, yields
\[
 W(x)=W_0(x)(1+\varepsilon_x),\qquad |\varepsilon_x|\leq\eta_G(\kk).
\]
Also $W_0(x)/(C_G\lambda^I)=Q_G(x)$. With $\overline\varepsilon=\EE_{Q_G}\varepsilon_X$, normalization gives
\[
 P_{G,\kk}(x)=Q_G(x)\frac{1+\varepsilon_x}{1+\overline\varepsilon}.
\]
Using the finite-space definition of total variation,
\[
 \TV(P_{G,\kk},Q_G)
 =\frac{\EE_{Q_G}|\varepsilon_X-\overline\varepsilon|}
        {2(1+\overline\varepsilon)}
 \leq\frac{\eta_G(\kk)}{1-\eta_G(\kk)}.
\]
The asserted limits follow from Corollary~\ref{cor:asymptotic}.
\end{proof}

\section{Consistency checks and the first correction}
\subsection{Paths and cycles}
The cubic identity gives $A_1=\lambda^4$ and $A_2=\lambda D$. Inserting a degree-two original vertex into an edge increases $m$ by one and decreases $I$ by one for the same expanded graph; its new factor $A_2$ cancels these changes in $C_G\lambda^I$. Thus the approximation does not depend on where a degree-two point on a path is designated as original.

For a single edge with $k$ internal vertices, the expanded graph is the path on $k+2$ vertices. The leading count is $\lambda^{k+8}/D$. For a base cycle with $r\geq3$ vertices, every degree is two, so the leading count is $\lambda^{I+r}$, as expected for a cycle on $I+r$ vertices. More explicitly, the circular binary-word transfer gives
\[
 |\MIS(C_N)|=\operatorname{tr}(T^N)
            =\lambda^N+\alpha^N+\overline\alpha^{\,N},\qquad N\geq3.
\]
These are consistency checks with established path and cycle enumeration, not new one-dimensional counting formulas.

\subsection{Equal lengths and an adjacency-sensitive term}
Keep $G$ fixed and set $k_e=k$ for every edge. For $d\geq1$, define
\begin{equation}\label{eq:bd}
 b_d(\alpha)=\alpha^2\lambda^{2d-2}
             +(1+\alpha)(1+\lambda)^{d-1}-1,
\end{equation}
and put
\begin{equation}\label{eq:HG}
 H_G(\alpha)=\frac{D}{2\alpha+3}
 \sum_{uv\in E}\frac{b_{d_u}(\alpha)b_{d_v}(\alpha)}{A_{d_u}A_{d_v}}.
\end{equation}
\begin{proposition}[First correction]\label{prop:correction}
As $k\to\infty$ with $G$ fixed,
\begin{equation}\label{eq:correction}
 \frac{M_G(k\boldsymbol1)}{C_G\lambda^{mk}}
 =1+2\Rea\!\left[H_G(\alpha)\left(\frac\alpha\lambda\right)^k\right]
    +O_G(\theta^{2k}).
\end{equation}
\end{proposition}
\begin{proof}
In~\eqref{eq:rootformula}, a coloring with exactly one edge $uv$ colored $\alpha$ and all other edges colored $\lambda$ changes the endpoint factors from $A_{d_u},A_{d_v}$ to $b_{d_u}(\alpha),b_{d_v}(\alpha)$. Dividing by the all-$\lambda$ summand and summing these contributions gives $H_G(\alpha)(\alpha/\lambda)^k$. The conjugate colorings give its complex conjugate. Every remaining coloring has at least two non-$\lambda$ edges; its normalized exponential factor has modulus at most $\theta^{2k}$. There are finitely many colorings and fixed coefficients, which proves the remainder estimate.
\end{proof}

The coefficient $H_G$ depends on the numbers of edges joining each pair of degrees. It can therefore distinguish graphs with the same degree sequence. It need not distinguish every such pair. In particular, $b_2(\alpha)=0$ by the cubic identities, so an edge incident to a degree-two original vertex makes no first-order contribution. Regular graphs of equal order and degree also have the same first coefficient.

\subsection{A connected degree-matched example}
Let $G_A$ be a triangle with a two-edge tail and $G_B$ be a four-cycle with a pendant leaf. Using vertex labels $0,1,2,3,4$, their edge sets are
\[
 E(G_A)=\{01,12,20,03,34\},\qquad
 E(G_B)=\{01,12,23,30,04\}.
\]
Both have degree multiset $(3,2,2,2,1)$ and five edges. Their common amplitude is
\[
 C=D^{-5}A_3A_2^3A_1=3.806096531012927\ldots.
\]
Every edge of $G_A$ meets a degree-two vertex, hence $H_{G_A}(\alpha)=0$. In $G_B$, only the pendant edge contributes, and
\[
 H_{G_B}(\alpha)=\frac{D}{2\alpha+3}\frac{b_3(\alpha)b_1(\alpha)}{A_3A_1}
 =-0.041381677565467-0.012334947674961\,i\ldots.
\]
The nonzero value can also be seen algebraically: $b_1(\alpha)=\alpha^4\ne0$ and $b_3(\alpha)=(\lambda^4-1)+\alpha(\lambda^6-\lambda^5)$ has a nonzero imaginary part. Table~\ref{tab:example} illustrates convergence of the count ratio despite different finite-length corrections.

\begin{table}[ht]
\centering
\caption{Exact counts for the two connected base graphs above, with $k$ new vertices on every edge. Ratios are rounded.}\label{tab:example}
\setlength{\tabcolsep}{10pt}
\begin{tabular}{r r r r}
\toprule
$k$ & $M_{G_A}(k\boldsymbol1)$ & $M_{G_B}(k\boldsymbol1)$ & $M_{G_A}/M_{G_B}$\\
\midrule
0 & 5 & 3 & 1.666666667\\
1 & 15 & 17 & 0.882352941\\
2 & 61 & 62 & 0.983870968\\
5 & 4\,305 & 4\,256 & 1.011513158\\
10 & 4\,860\,145 & 4\,854\,641 & 1.001133760\\
20 & 6\,206\,148\,196\,031 & 6\,206\,108\,377\,807 & 1.000006416\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The scale for growing base graphs}
The sufficient condition in Corollary~\ref{cor:asymptotic} is not necessary for every graph family. It does, however, have the correct uniform scale in the following sense.

\begin{proposition}[Failure at bounded error scale]\label{prop:sharpness}
There are pairs of growing base graphs with identical degree multisets, equal subdivision length $k$ on all edges, and $k\to\infty$, for which $m\theta^k$ stays bounded above and away from zero, but the ratio of their maximal-independent-set counts tends to $e$ or $e^{-1}$ rather than one. Thus neither $k\to\infty$ alone nor bounded $m\theta^k$ guarantees degree-sequence universality for all growing base graphs.
\end{proposition}
\begin{proof}
Use the connected graphs $G_A,G_B$ just described. Proposition~\ref{prop:correction}, their common amplitude, and $H_{G_A}=0$ give
\[
 \log\frac{M_{G_A}(k\boldsymbol1)}{M_{G_B}(k\boldsymbol1)}
 =c_k+O(\theta^{2k}),\qquad
 c_k=-2\Rea\!\left[H_{G_B}(\alpha)(\alpha/\lambda)^k\right].
\]
Write $\alpha/\lambda=\theta e^{i\phi}$ and $H_{G_B}(\alpha)=|H_{G_B}(\alpha)|e^{i\psi}$. Since $\alpha$ is nonreal, $e^{2i\phi}\ne1$. The finite geometric-sum identity therefore gives
\[
 \frac1N\sum_{k=1}^N\cos^2(k\phi+\psi)\longrightarrow\frac12.
\]
Infinitely many $k$ have $|\cos(k\phi+\psi)|\geq1/2$. Pass to an infinite subsequence on which $c_k$ has a fixed sign $s\in\{-1,1\}$. Along it,
\[
 |H_{G_B}(\alpha)|\theta^k\leq |c_k|
 \leq2|H_{G_B}(\alpha)|\theta^k.
\]
Let $r_k=\lfloor1/|c_k|\rfloor$, and take $r_k$ disjoint copies of $G_A$ and of $G_B$, respectively. The resulting graphs have identical degree multisets and $m=5r_k$ edges. Counts multiply over components, so the logarithm of their subdivided count ratio is
\[
 r_kc_k+O(r_k\theta^{2k})\longrightarrow s.
\]
Here $r_k|c_k|\to1$, $r_k\theta^{2k}\to0$, and $5r_k\theta^k$ is bounded above and away from zero. Exponentiation proves the claim.
\end{proof}

\section{Weighted enumeration and the size law}\label{sec:weighted}
The results of this section keep $G$ fixed. No growing-base-graph central limit theorem is asserted. Define the independent domination polynomial of the subdivided graph by
\[
 Z_G(\kk;z)=\sum_{S\in\MIS(G_{\kk})}z^{|S|}.
\]
Thus $Z_G(\kk;1)=M_G(\kk)$. Isolated original vertices contribute a factor $z$.

\subsection{Weighted boundary separation}
For $z\ne0$ near one, use
\[
 T(z)=\begin{pmatrix}0&z&0\\0&0&1\\1&z&0\end{pmatrix}.
\]
For states $p=(x,a)$ and $q=(y,b)$, the symmetric kernel that weights internal selected vertices, but not original endpoints, is
\begin{equation}\label{eq:weightedkernel}
 K_k(z)_{p,q}=z^{a-y}[T(z)^k]_{p,Rq}.
\end{equation}
Indeed the matrix transitions weight the appended vertices, including the far endpoint $y$ and excluding the first neighbor $a$; the prefactor corrects these two boundary weights. For $k=0$, any nonzero entry forces $a=y$, so this formula remains valid. At a selected original vertex one now inserts an additional factor $z$.

Let $\Rcal_z$ be the three roots of $r^3=z(r+1)$. They are distinct in a sufficiently small complex neighborhood of one. Right and left eigenvectors of $T(z)$ are
\[
 (1,r/z,r^2/z)^{\mathsf T}\quad\hbox{and}\quad(1,r^2,r),
\]
whose pairing is $2r+3$. Consequently
\begin{equation}\label{eq:weightedrankone}
 K_k(z)=\sum_{r\in\Rcal_z}\frac{r^k}{2r+3}\,w_r w_r^{\mathsf T},
 \qquad w_r=(1,r,r^2/z)^{\mathsf T}.
\end{equation}
The same local assembly as before proves the exact weighted formula
\begin{align}\label{eq:weightedroots}
 Z_G(\kk;z)
 &=\sum_{c:E\to\Rcal_z}
   \left(\prod_{e\in E}\frac{c(e)^{k_e}}{2c(e)+3}\right)
   \prod_{v\in V} F_v(c;z),\\
 F_v(c;z)
 &=z^{1-d_v}\prod_{e\ni v}c(e)^2
   +\prod_{e\ni v}(1+c(e))-1.\notag
\end{align}
For degree zero the factor is $z$. Although written using roots and negative powers of $z$, the expression equals the polynomial $Z_G(\kk;z)$ on its stated neighborhood. The kernel recurrence is $K_{k+3}(z)=zK_{k+1}(z)+zK_k(z)$, which is the familiar weighted path recurrence at the boundary level.

\subsection{An analytic asymptotic}
Let $\lambda(z)$ denote the analytic branch of $r^3=z(r+1)$ with $\lambda(1)=\lambda$, and write
\begin{align}\label{eq:Cz}
 A_d(z)&=z^{1-d}\lambda(z)^{2d}+(1+\lambda(z))^d-1,\\
 C_G(z)&=(2\lambda(z)+3)^{-m}\prod_{v\in V}A_{d_v}(z).\notag
\end{align}
\begin{lemma}\label{lem:analytic}
For fixed $G$ with $m>0$, there are $\epsilon>0$ and $q<1$ such that, uniformly for $|z-1|\leq\epsilon$ as $h=\min_e k_e\to\infty$,
\begin{equation}\label{eq:analytic}
 Z_G(\kk;z)=\lambda(z)^I C_G(z)\bigl(1+O_G(q^h)\bigr).
\end{equation}
The error is analytic on a neighborhood of this closed disk, and its derivatives of any fixed order satisfy the same type of estimate on a smaller disk.
\end{lemma}
\begin{proof}
All three roots are simple at $z=1$, so all admit analytic branches nearby. Shrink a closed disk about one until $\lambda(z)$, $C_G(z)$, and every denominator $2r(z)+3$ are nonzero, and the moduli of both other root-to-$\lambda(z)$ ratios are at most some $q<1$. This is possible by continuity and $C_G(1)>0$. In~\eqref{eq:weightedroots}, the all-$\lambda(z)$ coloring contributes $\lambda(z)^I C_G(z)$. Every other coloring has at least one edge with exponential ratio at most $q^h$; all its remaining factors are uniformly bounded on the disk. The finite sum proves~\eqref{eq:analytic}. Start with a slightly larger disk and then restrict to obtain the derivative assertion from Cauchy's estimates.
\end{proof}

\begin{theorem}[Gaussian size law for a fixed base graph]\label{thm:CLT}
Fix $G$ with at least one edge, and let $Y_{\kk}=|S|$ for a uniformly chosen $S\in\MIS(G_{\kk})$. If $\min_e k_e\to\infty$, then
\begin{equation}\label{eq:CLT}
 \frac{Y_{\kk}-\mu I}{\sqrt{\sigma^2 I}}
 \xrightarrow{\ d\ }\Normal(0,1),
\end{equation}
where
\begin{align}\label{eq:meanvariance}
 \mu&=\frac{\lambda+1}{2\lambda+3}
       =0.411495588662646\ldots,\\
 \sigma^2&=\frac{\lambda(\lambda+1)}{(2\lambda+3)^3}
       =0.017079629057537\ldots.\notag
\end{align}
More precisely, for some $q<1$,
\begin{align}\label{eq:moments}
 \EE Y_{\kk}&=\mu I+c_G+O_G(q^h),\\
 \Var(Y_{\kk})&=\sigma^2 I+v_G+O_G(q^h),\notag
\end{align}
where $c_G$ and $v_G$ are respectively the first and second derivatives at zero of $\log C_G(e^t)$.
\end{theorem}
\begin{proof}
The moment generating function is $Z_G(\kk;e^t)/Z_G(\kk;1)$. For sufficiently large $h$, on a fixed small complex neighborhood of zero, Lemma~\ref{lem:analytic} permits analytic logarithms and gives
\begin{align}\label{eq:logmgf}
 \log\EE e^{tY_{\kk}}
 &=I\bigl(\log\lambda(e^t)-\log\lambda\bigr)
   +\log C_G(e^t)-\log C_G(1)+O_G(q^h).
\end{align}
The error and its fixed-order derivatives are uniformly bounded as stated. If $r=\lambda(e^t)$, implicit differentiation of $r^3=e^t(r+1)$ yields
\[
 \frac{d}{dt}\log r=\frac{r+1}{2r+3},\qquad
 \frac{d^2}{dt^2}\log r=\frac{r(r+1)}{(2r+3)^3}.
\]
Differentiating~\eqref{eq:logmgf} at zero proves~\eqref{eq:moments}.

For fixed real $s$, substitute $t=is/\sqrt{\sigma^2 I}$ into~\eqref{eq:logmgf} and subtract $\mu It$. A Taylor expansion gives the leading term $-s^2/2$, a remainder $O(I^{-1/2})$ from the leading analytic function, an amplitude difference $O_G(I^{-1/2})$, and an error $O_G(q^h)$. Since $m>0$ and $h\to\infty$ imply $I\to\infty$, the characteristic functions converge to $e^{-s^2/2}$. The continuity theorem for characteristic functions proves~\eqref{eq:CLT}.
\end{proof}

The constants in~\eqref{eq:meanvariance} are the one-dimensional bulk constants, consistent with the renewal analysis of~\cite{KL}. Here the original graph changes the finite correction $C_G(z)$ while leaving the leading density and variance per added vertex unchanged. Centering by $\mu I$ rather than by $\mu(n+I)$ is harmless for a fixed graph, but the stated finite correction uses $I$ throughout.

\section{Reproducibility and scope}
\subsection{Computational checks}
The accompanying Python programs use only the standard library and implement two distinct checks: direct enumeration of independent dominating subsets of the actual expanded graph, and an exact boundary contraction on the original graph. The latter can be evaluated with three statuses per original vertex: selected, unselected with unrestricted neighboring states, and an inclusion--exclusion term subtracting the undominated choice. The status weights at $z=1$ are $1,1,-1$, and the corresponding half-edge supports are $\{10\}$, $\{00,01\}$, and $\{00\}$. At general $z$ the selected status has weight $z$.

One implementation passed 3\,300 unweighted graph--length comparisons, 386 weighted rational evaluations at $z=1/2$ or $2$, 152 exact first- and second-moment comparisons using rational second-order jets, 150 numerical spectral comparisons, and 16 example-count and first-correction checks. Its directly enumerated expanded graphs had at most 15 vertices. Separately written programs passed 2\,352 uniform-length and 1\,979 mixed-length count comparisons, 228 complete original-vertex joint-law histogram comparisons, and 456 rational weighted evaluations; they also checked cycles $C_3$ through $C_{17}$. The test families overlap and these totals are not counts of mutually distinct cases. Exact arithmetic is used for combinatorial counts and rational weighted checks; root-sum and error-constant checks use floating-point arithmetic.

The supplied source and result files record the tested families and reproduce the displayed examples. These computations detect errors in small cases and support reproducibility; the proofs above, rather than the finite tests, establish the general statements. The accompanying README identifies the test commands and distinguishes exact checks from numerical checks.

The project repository, including the reproducibility materials, is available at\\*
\url{https://github.com/dapyle11/long-subdivision-independent-sets}.

\subsection{Limitations and further questions}
The graph-uniform estimates concern unweighted enumeration and the original-vertex law. The analytic weighted expansion, the Gaussian limit, and the first correction have been proved here only with the base graph fixed. The first correction records degree-pair adjacency counts, not a complete graph invariant. Higher-order edge-color terms can contain more topology, but no general reconstruction result is claimed.

The condition $\sum_e\theta^{k_e}\to0$ is sufficient and need not be necessary for particular families, although Proposition~\ref{prop:sharpness} shows that bounded $m\theta^k$ cannot replace it as a uniform guarantee. Cancellation can yield much smaller errors, as the cycle formula and the vanishing of $b_2(\alpha)$ illustrate. Optimizing the universal constant, weakening the sufficient condition for particular graph classes, and obtaining useful higher-order formulas for growing base graphs remain separate questions. Loops and parallel edges are outside the stated graph class.

\section*{Authorship and research process disclosure}
Daniel A. Pyle initiated this research project. AI systems performed the technical derivations, computation, drafting, and internal review reported in this manuscript. Checks described as separate or independent refer to separate AI-assisted derivations or implementations, not to independent human mathematical verification. This draft has not been peer reviewed or checked with a formal proof assistant. No claim is made that the named author has completed a mathematical review of every argument; independent human review and a broader priority check are needed before submission.

\section*{License}
This manuscript is made available under the \href{https://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International license}. This notice applies to the manuscript; it does not assign an unstated software license to the accompanying code.

\begin{thebibliography}{9}
\bibitem{DPR}
L. Dall'Asta, P. Pin, and A. Ramezanpour, Statistical mechanics of maximal independent sets, \emph{Physical Review E} \textbf{80} (2009), 061136. \href{https://doi.org/10.1103/PhysRevE.80.061136}{doi:10.1103/PhysRevE.80.061136}. Open preprint: \href{https://arxiv.org/abs/0907.3309}{arXiv:0907.3309}.

\bibitem{Dod}
M. Dod, \emph{The Independent Domination Polynomial}, preprint (2016), \href{https://arxiv.org/abs/1602.08250}{arXiv:1602.08250}.

\bibitem{JA}
S. Jahari and S. Alikhani, On the independent domination polynomial of a graph, \emph{Discrete Applied Mathematics} \textbf{289} (2021), 416--426. \href{https://doi.org/10.1016/j.dam.2020.10.019}{doi:10.1016/j.dam.2020.10.019}. Open preprint: \href{https://arxiv.org/abs/1808.07369}{arXiv:1808.07369}.

\bibitem{KL}
P. L. Krapivsky and J. M. Luck, A renewal approach to configurational entropy in one dimension, \emph{Journal of Physics A: Mathematical and Theoretical} \textbf{56} (2023), 255001. \href{https://doi.org/10.1088/1751-8121/acd5bd}{doi:10.1088/1751-8121/acd5bd}. Open preprint: \href{https://arxiv.org/abs/2302.08852}{arXiv:2302.08852}.

\bibitem{Liu}
J.-G. Liu, X. Gao, M. Cain, M. D. Lukin, and S.-T. Wang, Computing solution space properties of combinatorial optimization problems via generic tensor networks, \emph{SIAM Journal on Scientific Computing} \textbf{45} (2023), A1239--A1270. \href{https://doi.org/10.1137/22M1501787}{doi:10.1137/22M1501787}. Open preprint: \href{https://arxiv.org/abs/2205.03718}{arXiv:2205.03718}.

\bibitem{Oh}
S. Oh, \emph{Maximal independent sets on a grid graph}, preprint (2017), \href{https://arxiv.org/abs/1709.03678}{arXiv:1709.03678}.
\end{thebibliography}
\end{document}