Concordance Graphs

Authors: Fishburn P.¹; Monjardet B.²

Source: European Journal of Combinatorics, Volume 21, Number 4, May 2000 , pp. 461-471(11)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

A graph G = (V, E) withn 2 vertices in V is a concordance graph if it has the same number of induced three-vertex one-edged subgraphs as induced three-vertex two-edged subgraphs. A concordance graph is proper if it is the comparability graph of a partially ordered set of order dimension 1 or 2. These definitions relate to the fact that the Kendall and Spearman correlation measures between linear orders L and L are equal if and only if the comparability graph of (V, L cap L) is a proper concordance graph. It is proved thatG is a concordance graph if and only if (n + 1) sum d_v + 12 t = 3 sum d_v², where d_vis the degree of vertex v andt is the number of induced K₃’s in G. This equation has been used to identify all concordance graphs and proper concordance graphs for n 7. Infinite families of proper concordance graphs are noted for each t in {0, 1, ctdot }, and an infinite family of regular concordance graphs is specified. It remains open as to whether any regular concordance graph that is neither edgeless nor complete is also proper. Copyright 2000 Academic Press

Language: English

Document Type: Research article

Affiliations: 1: AT&T Labs-Research, Florham Park, NJ 07932, U.S.A. 2: Cermsem, Université Paris I, 106-112 bd de l’Hopital, Paris Cédex 13, 75647, France

Publication date: 2000-05-01