On Edge Differential of Certain Families of Graphs

Hafiz Muhammad Afzal Siddiqui, Muhammad Usman, Syed Ajaz Kareem Kirmani and Michael Onyango Ojiema

Journal of Mathematics, 2025, vol. 2025, 1-9

Abstract: 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2025/6703477.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2025/6703477.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjmath:6703477

DOI: 10.1155/jom/6703477

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().