×

Niche graphs and mixed pair graphs of tournaments. (English) Zbl 0942.05027

The mixed pair graph of a tournament \(T\) is the graph with the same vertex set in which two vertices \(x\) and \(y\) are joined if and only if for every other vertex \(z\), either the arcs \(xz\) and \(zy\) or the arcs \(yz\) and \(zx\) are in \(T\). The authors characterize the graphs that are the mixed pair graph of some tournament.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, Linear Alg Applic 217 pp 5– (1995)
[2] Anderson, Cong Numer 93 pp 83– (1993)
[3] and p-niche graphs, to appear.
[4] Bowser, Cong Numer 76 pp 151– (1990)
[5] Bowser, Discrete Appl Math 30 pp 101– (1991)
[6] Cable, Discrete Appl Math 23 pp 231– (1989)
[7] Fishburn, J Graph Theory 16 pp 131– (1992)
[8] Fisher, J Graph Theory 29 pp 103– (1998)
[9] Fisher, Cong Numer 108 pp 97– (1995)
[10] Fisher, Proc S Korean Workshop Algebra Combin 16 pp 27–
[11] Gehrlein, Com Math Appl 27 pp 53– (1994)
[12] Gehrlein, Com Math Appl 32 pp 51– (1996)
[13] ?The competition number and its variants,?, Quo vadis, graph theory, and (Editors), Annal Discrete Math 55 (1993) 313-326. · doi:10.1016/S0167-5060(08)70396-0
[14] Kim, Linear Alg Appl 217 pp 167– (1995)
[15] ?Food webs, competition graphs, competition-common enemy graphs, and niche graphs,? Applications of combinatorics and graph theory to the biological and social sciences, (Editor), Volumes in mathematics and its applications, 17 Springer-Verlag, New York, 1989, pp. 221-244. · doi:10.1007/978-1-4684-6381-1_9
[16] Topics on tournaments, Holt, Rinehart and Winston, New York, 1968.
[17] and ?Tournaments,? and (Editors), Selected topics in graph theory, Academic, New York, 1979, pp. 169-204.
[18] Tournaments: Scores, kings, generalizations and special topics, surveys in graph theory, and (Editors), Cong Numer, 115 (1996), 171-211. · Zbl 0899.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.