Concordance Graphs

✍ Scribed by Peter Fishburn; Bernard Monjardet

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 205 KB
• Volume: 21
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1999.0368

✦ Synopsis

A graph G = (V, E) with n ≥ 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 ∩ L ) is a proper concordance graph. It is proved that G is a concordance graph if and only if (n+1)

, where d v is the degree of vertex v and t is the number of induced K 3 '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, . . .}, 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.