Metraipolis › archive › dc_772f1675b95e

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 — arXiv:2609.31818

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31818
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:22.885Z
SHA-256 of the archived text
26234da793cd2e2e32bf99fcf2186d792033a191af20e2063ee49cced8d11649
Stable URL of this page
https://metraipolis.com/documento/dc_772f1675b95e

How to cite

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 — arXiv:2609.31818 — arXiv (en), https://arxiv.org/abs/2609.31818 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_772f1675b95e (Metraipolis archive dc_772f1675b95e, sha256 26234da793cd2e2e32bf99fcf2186d792033a191af20e2063ee49cced8d11649)
BibTeX
@misc{dc772f1675b95e,
  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 — arXiv:2609.31818},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31818},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_772f1675b95e; sha256 26234da793cd2e2e32bf99fcf2186d792033a191af20e2063ee49cced8d11649},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31818. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Physics and Society (physics.soc-ph) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.31818 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.879Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).