Open access

Enumeration of 2-factored dominating sets in fixed-width grid graphs

M. Oo Natawat Klamsakul Nuttanon Songsuwan P. Kaemawichanurat

Jul 2026 · Journal of Combinatorial Mathematics and Combinatorial Computing · Vol 131, pp. 409-427 · 0 citations

TL;DR

The number of$2$-factored dominating sets on fixed-width grid graphs of dimensions $m \times n$, where the growth constant determined by the dominant singularity of the generating function is determined by the growth constant of the generating function.

Abstract

A $2$-factored dominating set ($2$fd-set) of a graph $G=(V,E)$ is a dominating set $F\subseteq V$ such that the induced subgraph $G[F]$ is $2$-regular, and hence is a disjoint union of cycles. In this study, $2$-factored dominating sets on fixed-width grid graphs of dimensions $m \times n$, where $m \in \{2,3,4\}$, are enumerated. We establish theorems describing the generating functions with respect to the number of $2$-factored dominating sets in these grid graphs. The number of $2$-factored dominating sets grows exponentially with $n$, with growth constant determined by the dominant singularity of the generating function.

DOI Semantic Scholar

Read PDF

Similar papers

Preprint Sep 2026

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...

Guo-Rong Gao, Jia-Lin He · 0 citations

Preprint Sep 2026

Local Fan-type obstructions and Ore-type conditions for rainbow Hamiltonicity in graph systems

Let $G=(G_1,...,G_n)$ be a graph system on a common $n$-vertex set $V$. For $v\in V$, set \[ \delta(v)=\min_{i\in[n]}d_{G_i}(v), \qquad E_{\cap}=\bigcap_{i=1}^n E(G_i), \] and let $d^c(u,v)$ denote the length of a shortest rainbow $u$--$v$ path. We study Hamiltonicity conditions imposed only on pairs at small rainbow d...

Ai-Lian Chen, Hao Chen · 0 citations

Preprint Sep 2026

A Tur\'an-type extremal problem for the number of spanning trees in $C_4$-free graphs

For a graph $F$, the Tur\'an number $\ex(n,F)$ is the maximum number of edges in an $F$-free graph on $n$ vertices. Let $q\ge 2$ be an integer and set $n=q^{2}+q+1$. Brown and Erd\H{o}s, R\'enyi and S\'os independently proved that $\ex(n,C_{4})\ge \frac12 q(q+1)^{2}$ for every prime power $q$, and F\"ured...

Shao-Han Xu, Feng-Ming Dong, Ke-Xiang Xu · 0 citations

Preprint Sep 2026

Unbalanced spectral Tur\'an problem for color-critical graphs with prescribed large maximum degree

Let $F$ be a connected color-critical graph with $\chi(F)=r+1\ge4$, let $S_{n,\Delta}^{(r)}=(n-\Delta)K_1\vee T(\Delta,r-1)$. We determine the graph of maximum adjacency spectral radius among all $n$-vertex $F$-free graphs with prescribed maximum degree $\Delta$. There is a constant $s_F\in[0,1)$ such that, for all suf...

Chang Liu · 1 citation

Preprint Sep 2026

Exact majority C-colourings of balanced Hamming graphs and grids

A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write $M(G)$ for the maximum number of classes. We determine $M(K_q^{\square(2k+1)})=\left\lfloor\frac{q^{k+1}}{\lfloor q/2\rfloor+1}\right\rfloor\qquad(q\ge3,\ k\ge0).$ The lower bound follows from explici...

Ze-Hua Lu · 0 citations

Preprint Sep 2026

Sharp edge-spectral supersaturation for odd cycles

Let $G$ be a graph with $m$ edges and adjacency spectral radius$\rho(G)$, and let $N(C_{2k+1},G)$ denote the number of copies of $C_{2k+1}$ in $G$. For each fixed integer $k\ge 2$, define $ g_k(m):=\frac{k-1+\sqrt{4m-k^2+1}}{2}. $ Li, Zhai and Shu [European J. Combin., 2024] determined the spectral extr...

Jia-Qi Liu, Zhenzhen Lou, Shuang Sun · 1 citation