The Interchange Graphs of Tournaments with Minimum Score Vectors Are Exactly Hypercubes

被引：4

作者：

Chen, An Hang ^{[2
]}

Chang, Jou Ming ^{[2
]}

Wang, Yue Li ^{[1
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

[2] Natl Taipei Coll Business, Dept Informat Management, Taipei, Taiwan

来源：

GRAPHS AND COMBINATORICS | 2009年 / 25卷 / 01期

关键词：

Tournaments; Score vectors; Interchange graphs; Hypercubes;

D O I：

10.1007/s00373-008-0818-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A Delta-interchange is a transformation which reverses the orientations of the arcs in a 3-cycle of a digraph. Let T(S) be the collection of tournaments that realize a given score vector S. An interchange graph of S, denoted by G(S), is an undirected graph whose vertices are the tournaments in T(S) and an edge joining tournaments T, T' is an element of T(S) provided T' can be obtained from T by a Delta-interchange. In this paper, we find a set of score vectors of tournaments for which the corresponding interchange graphs are hypercubes.

引用

页码：27 / 34

页数：8

共 11 条

[1]

[Anonymous], 1968, Topics on Tournaments

[2]

BRUALDI RA, 1984, PROGR GRAPH THEORY, P128

[3]

Chartrand Gary, 2005, Introduction to Graph Theory

[4]

GIBSON PM, 1984, J COMB THEORY B, V36, P240, DOI 10.1016/0095-8956(84)90030-3

[5] THEORY OF ROUND ROBIN TOURNAMENTS [J].

HARARY, F ;

MOSER, L .

AMERICAN MATHEMATICAL MONTHLY, 1966, 73 (03) :231-&

[6]

Kannan R, 1999, RANDOM STRUCT ALGOR, V14, P293, DOI 10.1002/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO

[7]

2-G

[8]

LANDAU H. G., 1953, BULL MATH BIOPHYS, V15, P143, DOI 10.1007/BF02476378

[9]

Lovasz L., 1993, Combinatorial Problems and Exercises

[10]

MCSHINE L, 2000, ELECT J COMB, V7

← 1 2 →