Connected dom-forcing Sets in Graphs

2025

Read Connected dom-forcing Sets in Graphs (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-2505-11038.txt.

Introduction

Susanth P, Charles Dominic, and Premodkumar study a new graph measure that mixes domination with a forcing game, in this 2025 paper. The catalog names no authors; the byline in the text gives the three names above. A dom-forcing set must cover every vertex while also seeding a spread that can fill the graph under the forcing rule.

The connected version adds one demand: the chosen set itself must form one unbroken piece. The paper probes the traits of this smallest size and pins it down for several classic graphs. Products of graphs get exact values too. The authors add the measure to the toolkit for network control questions.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11038

Browse the full library · About the Tower of Babel

Full text

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

Connected dom-forcing Sets in Graphs Abstract . In a graph G G , a dominating set D f ⊆ V ⁡ ( G ) D_{f}\subseteq V(G) is called a dom-forcing set if the sub-graph induced by ⟨ D f ⟩ \langle D_{f}\rangle must form a zero forcing set. The minimum cardinality of such a set is known as the dom-forcing number of the graph G G , denoted by F d ​ ( G ) F_{d}(G) . A connected dom-forcing forcing set of a graph G G , is a dom-forcing set of G G that induces a sub graph of G G which is connected. The connected dom-forcing number of G, F c ​ d ​ ( G ) F_{cd}(G) , is the minimum size of a connected dom-forcing set. This study delves into the concept of the connected dom-forcing number F c ​ d ​ ( G ) F_{cd}(G) , examining its properties and characteristics. Furthermore, it seeks to accurately determine F c ​ d ​ ( G ) F_{cd}(G) for several well-known graphs and their graph products. AMS Subject Classification: 05C50, 05C69, 05C12. Key Words: Zero forcing number, Connected zero forcing number, Domination number, Connected domination number, Dom-forcing number, Connected Dom-forcing number. Susanth P 1,2 Charles Dominic 3 Premodkumar K P 4 1 Department of Mathematics , Pookoya Thangal Memorial Government College, (Affiliated to University of Calicut) Perinthalmanna, Kerala- 679322, INDIA. 2 Department of Mathematics St.Joseph’s College(Autonomous), Devagiri, Calicut - 673008, INDIA. 3 Flat 3, Stone Bridge House, Stonebridge walk, Chelmsford, CM1 1DN, Essex, United Kingdom. 4 Department of Mathematics , Govt. College Malappuram , Kerala- 676509, INDIA. 1,2 E-mail: [email protected] 3 E-mail: [email protected] 4 E-mail: [email protected] 1. Introduction A zero forcing set contains certain vertices in a graph that are initially colored black after applying the following color-change rule. Color-change rule: Let G be a graph with each vertex is colored either white or black, u be a black vertex of G , and exactly one neighbor v of u be white. Then change the color of v to black. When this rule is applied, we say u forces v , and write u\rightarrow v see [ 1 ] . A zero forcing set ( or \mathcal{ZFS} for brevity) of a graph G is a subset Z of vertices such that if initially the vertices in Z are colored black and remaining vertices are colored white, the entire graph G may be colored black by repeatedly applying the color-change rule. The minimum |Z| over all zero forcing sets Z\subset G is called the zero forcing number and is denoted by Z(G) .Any zero forcing set of order Z(G) is called a minimum zero forcing set [ 1 ] . A connected zero forcing set ( or \mathcal{CZFS} for brevity) of a graph G , is a zero forcing set of G that induces a sub graph of G which is connected. The connected zero forcing number of G , Z_{c}(G) , is the minimum size of connected zero forcing sets. Any connected zero forcing set of order Z_{c}(G) is called a minimum connected zero forcing set [ 6 ] . A subset D of vertex set V(G) in a graph G=(V,E) is referred a dominating set if every vertex v\in V(G) is either an element of D or as at least one neighbor in D see [ 13 ] . If a sub graph formed by the vertices of a dominating set in a graph G is connected then the set is called a connected dominating set. A minimum connected dominating set of a graph G is a connected dominating set with the smallest possible cardinality among all connected dominating sets of G . The connected domination number of G is the number of vertices in the minimum connected dominating set, and is denoted by \gamma_{c}(G) [ 3 ] . A set D_{f}\subseteq V of vertices is called a dom-forcing set if it satisfies the following two conditions. i) D_{f} must form a dominating set. ii) D_{f} must form a zero forcing set. The minimum cardinality of such a set is called the dom-forcing number of the graph G and is denoted by F_{d}(G) [ 12 ] . This study integrates the concepts of connected domination and connected zero forcing to introduce a new graph-theoretic parameter: the connected dom-forcing set. In this article we consider only connected graphs. 2. motivation Zero forcing and domination are two independently rich and fundamental concepts in graph theory that each have significant applications to problems in network theory, quantum control of systems, power grid surveillance, and information spreading. Domination reflects the notion of local influence—forcing all vertices to be either in a chosen set or within distance one of it—while zero forcing describes how influence spreads throughout a network from a minimal starting set. The concept of a dom-forcing set comes naturally as a synthesis of these two concepts. It’s a vertex set that not only has immediate control over the graph (by domination) but also sets off a process that ends up forcing the whole network (by zero forcing). By combining these ideas, dom-forcing sets form a more robust tool to study how influence can be gained and extended within intricate systems. The addition of connected dom-forcing sets brings in yet another essential aspect—connectivity. In actual networks like communication infrastructures, biological systems, and social networks, connectedness of the initial control set is generally necessary for resilience, coordination, and effective transmission of information. A connected dom-forcing set guarantees that influence is not merely exhaustive but also structurally connected and resilient against interference. Investigating dom-forcing sets and their related variants opens a rich class of mathematical problems, such as finding bounds, describing extremal instances, and studying their relation to traditional graph invariants like the domination number and zero forcing number. Such studies also enable practical applications in which efficient control needs to reconcile immediate influence, dynamic spread, and structural robustness. In conclusion, the study of dom-forcing sets is driven by its theoretical value as well as by its prospects for solving practical problems in network control more exactly and effectively. 3. Connected dom-forcing set In this section, we explore the idea of a connected dom-forcing set. Additionally, we do a comparison between the dom-forcing set and the connected dom-forcing set in the context of specific types of graphs. Definition 3.1 . A set CD_{f}\subseteq V of vertices is called a connected dom-forcing set if it satisfies the following two conditions. i) \langle CD_{f}\rangle must form a connected dominating set. ii) \langle CD_{f}\rangle must form a connected zero forcing set. The minimum cardinality of such a set is called the connected dom-forcing number of the graph G and is denoted by F_{cd}(G) . For instance, contemplate the graph C_{5} illustrated in Figure 1. u_{1} u_{2} u_{3} u_{4} u_{5} Figure 1 . In this graph C_{5} , CD_{f}=\{u_{1},u_{2},u_{3}\} is a connected dominating as well as zero forcing set and no subset of the vertex set with cardinality less than three has this property so F_{cd}(C_{5})=3 The focus of this article is on determining the connected dom-forcing number, F_{cd}(G) , for various well-known graphs and their specific products, including the corona product, rooted product,

Read the complete text