Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area
Abstract
This study addresses a theoretical model regarding equity and accessibility challenges in designing shared transportation systems (such as micro-mobility networks) by applying graph-vertex domination setting. The work focuses on identifying dominating forced vertices, that represent nodes belonging to every dominating set of a graph of the smallest possible cardinality, and which correspond to critical, non-negotiable station locations essential for maintaining system efficiency and coverage. From a theoretical perspective, in the paper it is first demonstrated that determining whether a given vertex is a dominating forced vertex is co-NP-hard, establishing the computational infeasibility of exact identification in large networks. To analyze graph structures, sharp theoretical bounds on the maximum number of dominating forced vertices are established, proving that their count is bounded above by one-third of the order of the graph, and provide complete structural characterizations for graphs achieving this bound, as well as, trees with no dominating forced vertices. To overcome computational limits in practical urban settings, the study uses an iterated greedy metaheuristic framework to generate minimal dominating sets and approximate critical forced nodes based on their appearance frequency across iterations. The methodology is validated on strong grid graphs and applied to real-world road network models of Algeciras and La Línea de la Concepción, two cities in the area of Campo de Gibraltar, Spain, which successfully pinpoints candidate location points for scooter-sharing stations across both cities.
Related
- The minimum number of vertices of a triangulation of ℝℙ5
- On the Vertices That Belong to All Minimum Identifying Codes
- Dominating Reals and Ordinal Theories
- Notes on efficient dominating sets and efficient open dominating sets in circulant graphs
- Triebel - Lizorkin spaces of dominating mixed smoothness are algebras with respect to pointwise multiplication
BibTeX
@misc{farhan2026vertices,
title = {{Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area}},
author = {Mohammad Farhan and Dorota Kuziak and Iztok Peterin and Ismael G. Yero},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31818},
eprint = {2609.31818},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31818},
}
RIS
TY - UNPB
TI - Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area
AU - Mohammad Farhan
AU - Dorota Kuziak
AU - Iztok Peterin
AU - Ismael G. Yero
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31818
UR - https://arxiv.org/abs/2609.31818
AB - This study addresses a theoretical model regarding equity and accessibility challenges in designing shared transportation systems (such as micro-mobility networks) by applying graph-vertex domination setting. The work focuses on identifying dominating forced vertices, that represent nodes belonging to every dominating set of a graph of the smallest possible cardinality, and which correspond to critical, non-negotiable station locations essential for maintaining system efficiency and coverage. From a theoretical perspective, in the paper it is first demonstrated that determining whether a given vertex is a dominating forced vertex is co-NP-hard, establishing the computational infeasibility of exact identification in large networks. To analyze graph structures, sharp theoretical bounds on the maximum number of dominating forced vertices are established, proving that their count is bounded above by one-third of the order of the graph, and provide complete structural characterizations for graphs achieving this bound, as well as, trees with no dominating forced vertices. To overcome computational limits in practical urban settings, the study uses an iterated greedy metaheuristic framework to generate minimal dominating sets and approximate critical forced nodes based on their appearance frequency across iterations. The methodology is validated on strong grid graphs and applied to real-world road network models of Algeciras and La Línea de la Concepción, two cities in the area of Campo de Gibraltar, Spain, which successfully pinpoints candidate location points for scooter-sharing stations across both cities.
ER -