Irreversible k k -Threshold Conversion Number of Corona Product and Double Corona Product Graphs

Eric Moon, Paul Flesher, Soumya Bhoumik · 2025

Read Irreversible k k -Threshold Conversion Number of Corona Product and Double Corona Product Graphs by Eric Moon, Paul Flesher, Soumya Bhoumik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21764.txt.

Introduction

Eric Moon and co-authors study how a spreading process takes over certain built up graphs, in a math paper from 2025. In the process, a seed set of active points wakes its neighbors once enough of them are active, and the wake up cannot be undone. The smallest seed set that wakes the whole graph is the number the team wants.

Their graphs are corona products, formed by hanging copies of one graph off each point of another. Exact results are found for the single and double forms by shrinking them to smaller cases. A broader base form unifies both cases in one frame. The authors also ask how likely a random smallest seed set is to wake the whole graph, which shows how layered build shapes the spread.

Catalog record

CREATOREric Moon, Paul Flesher, Soumya Bhoumik
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-21764

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Irreversible k k -Threshold Conversion Number of Corona Product and Double Corona Product Graphs Eric Moon, Paul Flesher, Soumya Bhoumik Abstract This paper studies the irreversible k k -threshold process on graphs, where a vertex becomes colored if at least k k neighbors are colored and remains colored indefinitely. We investigate vertex sets that, when initially colored, lead to a completely colored graph. The graphs under initial consideration are constructed using the corona product of cyclic graphs and complete graphs. We then introduce and explore double corona product graphs (of cyclic graphs and complete graphs) to study more complex topologies and their impact on the coloring propagation. We further extend the theory by introducing a probabilistic approach to the coloring dynamics. Our findings provide insights into the interplay between graph structure and saturation dynamics by extending the theory to new families of graphs and introducing a probabilistic approach with potential applications in epidemiology and social influence modeling. Keywords. irreversible k -threshold, k -inconvertible, conversion set, graph reduction 1 Introduction The propagation of influence in networks is a fundamental topic in graph theory with applications in epidemiology, opinion dynamics, and social networks. The irreversible k -threshold process models such phenomena by coloring a vertex if at least k of its neighbors are colored, after which it remains colored permanently. A key problem in this area is the determination of initial sets that, if colored, lead to a completely colored graph under the irreversible k -threshold process and then determining the minimum size of such a set. Numerous researchers have investigated this problem across various families of graphs. Dreyer and Roberts [ 1 ] were the first to explore this topic, analyzing the process in several well-known graph families, including regular graphs, cycles, paths, trees, grid graphs, and complete bipartite graphs. Building on this foundation, Abiad et al. extended the investigation to include certain product families of graphs, such as Cartesian, tensor, strong, and lexicographic products (see [ 5 ] ). For readers interested in further developments, additional results can be found in [ 2 , 3 , 4 ] . In this paper, we examine the k -threshold conversion process in corona product graphs C_{n}\odot K_{p} . These (corona) product graphs provide a natural framework for modeling structures found in epidemiology and social networking, yet their role in threshold dynamics has not been thoroughly investigated. In addition, we introduce a natural extension by defining and analyzing double corona graphs C_{n}\mathbin{\circledcirc}K_{p} that exhibit increased structural complexity and distinct spreading behaviors. We further extend the theory by introducing a probabilistic approach to analyzing the coloring dynamics on these families of graphs. Our main results establish necessary and sufficient conditions for complete graph coloring in these graph families, identify the smallest sets of colored vertices that can color the entire graph, and demonstrate the impact of randomness on coloring dynamics. This study offers new insights into both theoretical and applied aspects of contagion dynamics by characterizing threshold conversion sets and extending the analysis to probabilistic settings. These findings contribute to a deeper understanding of influence propagation in structured networks, with implications for controlling disease spread, optimizing marketing strategies, and designing resilient network architectures. We conclude with several key definitions, remarks, and results established elsewhere. The irreversible k -threshold conversion process on a graph G(V,E) is an iterative procedure that begins with an initial set S_{0}\subseteq V of colored vertices. At each step t\ (t=1,2,\cdots) , the set S_{t} is formed by including all vertices that have at least k colored neighbors in S_{t-1} . The initial set S_{0} is known as the seed set of the k -threshold conversion process and is termed an irreversible k -threshold conversion set (IkCS) of G if, for some t\geq 0 , S_{t}=V(G) . The smallest possible size of an IkCS in G is called the irreversible k -threshold conversion number of G , denoted by C_{k}(G) . If C_{k}(G)=|V(G)| , G is called k- inconvertible. Remark 1.1 Let G=(V,E) be a graph, and let S_{0}\subset V be an IkCS, then the set U of vertices in G with degree less than k is contained in S_{0} ; that is, U=\{v\in V:\deg(v)<k\}\subseteq S_{0}\subset V. Proposition 1.2 [ 1 ] For the cyclic graph C_{n} , C_{2}(C_{n})=\lceil{\frac{n}{2}}\rceil The rest of this paper is organized as follows. In Section 2 , we investigate the k -threshold number for the family of corona products of C_{n} and K_{p} . Next, in Section 2.2 we analyze the probability that a random C_{k} -coloring of C_{n}\odot K_{p} results in a complete coloring of the graph. Finally, in Section 3 we extend the definition of the corona product to introduce the double corona product and study its k -threshold number. 2 Corona Product: C_{n}\odot K_{p} The corona product G_{1}\odot G_{2} of two graphs is the graph obtained by taking one copy of G_{1} , and p_{1} copies of G_{2} (where |V(G_{1})|=p_{1} ), and then joining the i^{\rm th} vertex of G_{1} by an edge to every vertex in the i^{\rm th} copy of G_{2} . The number of vertices of C_{n}\odot K_{p} is n(p+1) , and number of edges are n\left({p(p+1)}/{2}+1\right) . In the graph G=C_{n}\odot K_{p} , let V=\{v_{i}|1\leq i\leq n\}\cup\{u_{i}^{j}|1\leq i\leq n,1\leq j\leq p\} , where v_{i} denote the vertices of C_{n} (we refer them as inner vertices), and u_{i}^{j} represents the j^{\text{th}} vertex of the i^{\text{th}} copy of K_{p} that is connected with v_{i} vertex of C_{n} . We will refer to I=\{v_{1},v_{2},\cdots,v_{n}\} as the inner vertices, and B=\{u_{i}^{j}\,1\leq j\leq p\} as the i^{\rm th} block. 2.1 k -threshold of C_{n}\odot K_{p} We begin by presenting a Reduction Lemma, followed by an explicit construction of C_{k}(C_{n}\odot K_{p}) for all admissible values of k . Lemma 2.1 C_{k}(C_{n}\odot K_{p})=r\cdot n+C_{k-r}(C_{n}\odot K_{p-r}) where r=\min\{(k-1),p\} . Proof. Naturally, when k\leq p , each block in S_{0} must contain at least (k-1) vertices to ensure the graph can be completed. If k>p , all p vertices in each block are necessary. Thus, every vertex—whether part of a block or the cycle—is adjacent to at least (k-1) colored vertices (those in its associated block). Given this structure, whenever k\leq p , the problem can be simplified by considering the residual graph obtained after removing exactly k-1 colored vertices from each block, resulting in a total of (k-1)\cdot n colored vertices being removed. The resulting graph C_{n}\odot K_{p-(k-1)} then requires only a threshold of 1 for completion. On the other hand, if k>p , all p vertices in each block are removed. The problem then reduces to completing the cycle C_{n} under a threshold of k-p . Therefore, we obtain the recurrence: C_{k}(C_{n}\odot K_{p})=\begin{cases}(k-1)n+C_{1}(C_{n}\odot K_{p-(k-1)}),&\text{if }k<p+1,\\ pn+C_{k-p}(C_{n}),&\text{if }k\geq p+1.\end{cases} ∎ \circ \circ \circ \circ \circ \circ \circ \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ C_{3}(C_{8}\odot K_{3}) \circ \circ \circ \circ \circ \circ \circ \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ \bullet \bullet \circ C_{3-2}(C_{8}\odot K_{3-2}) \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ C_{1}(C_{8}\odot K_{1}) Figure

Read the complete text