DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2013-10-10 - Article/Dans un journal avec peer-review - Anglais - 26 page(s) (Soumise)

Absil Romain , Mélot Hadrien , "On price of symmetrisation" in Discrete Applied Mathematics

  • Edition : Elsevier Science, Amsterdam (The Netherlands)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématique et Recherche opérationnelle (F151), Algorithmique (S825)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)

Abstract(s) :

(Anglais) We introduce the price of symmetrisation, a concept that aims to compare fundamental differences (gap and quotient) between values of a given graph invariant for digraphs and the values of the same invariant of the symmetric versions of these digraphs. Basically, given some invariant our goal is to characterise digraphs that maximise price of symmetrisation. In particular, we show that for some invariants, as diameter or domination number, the problem is easy. The main contribution of this paper is about (partial) results on the price of symmetrisation of the average distance. It appears to be much more intricate than the simple cases mentioned above. First, we state a conjecture about digraphs that maximise this price of symmetrisation. Then, we prove that this conjecture is true for some particular class of digraphs (called bags) but it remains open for general digraphs. Moreover, we study several graph transformations in order to remove some configurations that do not appear in the conjectured extremal digraphs.

Identifiants :
  • arXiv : 1310.2775