Academic Journal
ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and G$^2$-connected medians
| العنوان: | ABC(T)-graphs: an axiomatic characterization of the median procedure in graphs with connected and G$^2$-connected medians |
|---|---|
| المؤلفون: | Bénéteau, Laurine, Chalopin, Jérémie, Chepoi, Victor, Vaxès, Yann |
| المساهمون: | Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Algorithmique Distribuée (DALGO), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017) |
| المصدر: | ISSN: 0166-218X ; Discrete Applied Mathematics ; https://hal.science/hal-03714728 ; Discrete Applied Mathematics, 2024, 359, pp.55--74. ⟨10.1016/j.dam.2024.07.023⟩. |
| بيانات النشر: | HAL CCSD Elsevier |
| سنة النشر: | 2024 |
| المجموعة: | Aix-Marseille Université: HAL |
| مصطلحات موضوعية: | Median function, facility location, consensus function, axiomatic approach, graph distances, unimodality, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG] |
| الوصف: | International audience ; The median function is a location/consensus function that maps any profile $\pi$ (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices from $\pi$. The median function satisfies several simple axioms: Anonymity (A), Betweeness (B), and Consistency (C). McMorris, Mulder, Novick and Powers (2015) defined the ABC-problem for consensus functions on graphs as the problem of characterizing the graphs (called, ABC-graphs) for which the unique consensus function satisfying the axioms (A), (B), and (C) is the median function. In this paper, we show that modular graphs with $G^2$-connected medians (in particular, bipartite Helly graphs) are ABC-graphs. On the other hand, the addition of some simple local axioms satisfied by the median function in all graphs (axioms (T), and (T$_2$)) enables us to show that all graphs with connected median (comprising Helly graphs, median graphs, basis graphs of matroids and even $\Delta$-matroids) are ABCT-graphs and that benzenoid graphs are ABCT$_2$-graphs. McMorris et al (2015) proved that the graphs satisfying the pairing property (called the intersecting-interval property in their paper) are ABC-graphs. We prove that graphs with the pairing property constitute a proper subclass of bipartite Helly graphs and we discuss the complexity status of the recognition problem of such graphs. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| Relation: | info:eu-repo/semantics/altIdentifier/arxiv/2206.03587; ARXIV: 2206.03587 |
| DOI: | 10.1016/j.dam.2024.07.023 |
| الاتاحة: | https://hal.science/hal-03714728 https://hal.science/hal-03714728v2/document https://hal.science/hal-03714728v2/file/2206.03587v2.pdf https://doi.org/10.1016/j.dam.2024.07.023 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.C73315DA |
| قاعدة البيانات: | BASE |
| DOI: | 10.1016/j.dam.2024.07.023 |
|---|