On graphs associated to sets of rankings.

Regino Criado ^[1] ; Esther García ^[1] ; Francisco Pedroche ^[2] ; Miguel Romance ^[1]
1. [1] Universidad Rey Juan Carlos
  
  Universidad Rey Juan Carlos
  
  Madrid, España
2. [2] Universidad Politécnica de Valencia
  
  Universidad Politécnica de Valencia
  
  Valencia, España
Localización: Journal of computational and applied mathematics, ISSN 0377-0427, Vol. 291, Nº 1 (1 January 2016), 2016, págs. 497-508
Idioma: inglés
DOI: 10.1016/j.cam.2015.03.009
Enlaces
- Texto completo
Resumen
- In this paper we analyze families of rankings by studying structural properties of graphs. Given a finite number of elements and a set of rankings of those elements, two elements compete when they exchange their relative positions in at least two rankings, and we can associate an undirected graph to a set of rankings by connecting elements that compete. We call this graph a competitivity graph. Competitivity graphs have already appeared in the literature as co-comparability graphs, ff-graphs or intersection graphs associated to a concatenation of permutation diagrams. We introduce certain important sets of nodes in a competitivity graph. For example, nodes that compete among them form a competitivity set and nodes connected by chains of competitors form a set of eventual competitors. These sets are analyzed and a method to obtain sets of eventual competitors directly from a set of rankings is shown.