CYCLE DOMINATION POLYNOMIAL OF A GRAPH
Advances and Applications in Discrete Mathematics · 14.04.2026 · 43 (3) · 363-379
DOI: 10.17654/0974165826024 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances and Applications in Discrete Mathematics, online erschienen am 14.04.2026. Verfasst von M. P. Shyama. Die Arbeit nennt 10 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Let $G(V, E)$ be a simple connected finite graph. Then a Hamilton path in a graph is a path that reaches every vertex, and a Hamilton cycle is a cycle that reaches every vertex. A graph with a Hamilton cycle is called Hamiltonian. A dominating set $S\subseteq V$ is said to be a cycle dominating set if the induced subgraph $\langle S \rangle$ is Hamiltonian. The min-cycle domination number of $G$, denoted by $\gamma_{\text {min}_{\circ}}(G)$, is the minimum cardinality of the cycle dominating sets in $G$ and the max-cycle domination number of $G$, denoted by $\gamma_{\text {max}_{\circ}}(G)$ is the maximum cardinality of the cycle dominating sets in $G$. Note that the min-cycle domination number of $G$ is at least 3 and the max-cycle domination number of $G$ is at most $|V(G)|$. Let $\mathcal D_\circ (G, i)$ be the family of cycle dominating sets of $G$ with cardinality $i$ and let $d_\circ(G, i) = |\mathcal D_\circ (G, i)|$. The polynomial $D_{\circ}(G, x) = \sum_{i = \gamma_{\min_{\circ}}(G)}^{\gamma_{\max_{\circ}}(G)}d_{\circ}(G, i) x^i$ is defined as the cycle domination polynomial of $G$. A root of $D_\circ(G, x)$ is called a cycle domination root of $G$. We obtain some basic properties of the cycle domination polynomial and compute this polynomial and its roots for some specific graphs. Received: November 18, 2025Revised: December 6, 2025Accepted: February 23, 2026
Zitieren
APA
Shyama, M. P. (2026). CYCLE DOMINATION POLYNOMIAL OF A GRAPH. Advances and Applications in Discrete Mathematics, 43(3), 363-379. https://doi.org/10.17654/0974165826024
Vancouver
Shyama MP. CYCLE DOMINATION POLYNOMIAL OF A GRAPH. Advances and Applications in Discrete Mathematics. 2026;43(3):363-379. doi:10.17654/0974165826024
BibTeX
@article{Shyama2026,
author = {Shyama, M. P.},
title = {CYCLE DOMINATION POLYNOMIAL OF A GRAPH},
journal = {Advances and Applications in Discrete Mathematics},
year = {2026},
volume = {43},
number = {3},
pages = {363--379},
doi = {10.17654/0974165826024}
}
EUVIMED