On the differential in central operator đ( G )
Open Access
- 20 May 2026
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 60  (3) , 1419-1437
Abstract
The central operator đ( G ) is a structural transformation that combines edge subdivision with the complementation on the original vertex set. In this paper, we characterize the behavior of the differential â(đ( G )), an invariant that measures the maximum influence potential of a network. We establish sharp bounds for â(đ( G )) in terms of the order n and the maximum degree Î( G ) of the base graph, proving a guaranteed growth property: for any connected graph of order n â„ 4, â(đ( G )) â„ â( G Ì)+1. Our structural analysis reveals a parsimony property of optimal sets. Specifically, Theorem 3.16 shows that minimum differential sets in đ( G ) are primarily supported on the original vertex set V , effectively reducing the search space for optimization algorithms. Furthermore, in Theorem 3.22 we establish a notable theoretical convergence by identifying conditions under which the central, subdivision, and â( G ) operators yield the same differential value, namely m + n â 4. Finally, we provide exact evaluations for several fundamental graph families and derive Nordhaus-Gaddum type inequalities (Prop. 3.24 and Cor. 3.25) for the class of trees. These results clarify how the central operator enhances the diffusion capacity of networks, thereby bridging the gap between topological transformations and practical influence maximization.Keywords
This publication has 26 references indexed in Scilit:
- The differential on graph operator R(G)RAIRO - Operations Research, 2024
- Total Domination on Tree OperatorsMediterranean Journal of Mathematics, 2022
- The differential of the line graph L(G)Discrete Applied Mathematics, 2022
- From the Strong Differential to Italian Domination in GraphsMediterranean Journal of Mathematics, 2021
- Domination related parameters in the generalized lexicographic product of graphsDiscrete Applied Mathematics, 2021
- On the 2-Packing Differential of a GraphResults in Mathematics, 2021
- Double domination in lexicographic product graphsDiscrete Applied Mathematics, 2020
- Lower bounds on the differential of a graphDiscrete Mathematics, 2012
- Influential Nodes in a Diffusion Model for Social Networks2005
- Some properties of line digraphsRendiconti del Circolo Matematico di Palermo Series 2, 1960