On Edge Differential of Certain Families of Graphs

This paper presents and examines a new game of combinatorial optimisation that can be defined on any graph. A player can buy any number k of tokens in this game for $1 apiece, and then place them on a selected subset of k edges in G. The player earns $1 from the bank for each edge that is next to at least one edge with a token but is not selected. Finding a token placement strategy that maximises net profit which is determined by subtracting the cost of the tokens from the total payout from the bank, is the goal. We present the edge differential of a graph, a parameter that captures the highest profit possible under ideal token placement, to formalise this optimisation problem. Assume that BX is the collection of edges in E∖X that are adjacent to an edge in X. We define the edge differential of a set X as follows: ∂EX=BX−X based on this game. Hence, for any subset X⊆E, the edge differential of a graph is defined as follows: ∂EG=max∂EX. We calculate the edge differential for a number of well-known graph families, such as the triangular ladder graphs, comb, ladder, complete, star, double star, path, cycle, wheel, and complete bipartite graphs. This concept leads to intriguing relationships between influence propagation in graphs and edge domination. We illustrate the significance of the edge differential in numerous real-world domains and continue to explore its theoretical characteristics.