中文摘要
競賽圖是一個完全圖且圖形中的每個邊都具有方向性，若Tn 代表n 個點的競賽圖，在圖中若點x 打敗點y 則表示為x → y。令Tn 中點x 打敗其他點的個數稱為點x 的得分。得分向量則是將所有在Tn 中點的得分以非遞減數列方式排列。

在競賽圖中若某點x 被稱為『王』，表示x 若不是可直接打敗所有點y，便是可間接透過第三者z 來打敗y（即x → z 且z → y）。若令b(x, y) 表示x 間接透過第三者打敗y的數量。在競賽圖中若點x 滿足下面定義則被稱為『強勢王』：點x 要擊敗所有點y 或是當y → x 時仍然要有b(x, y) > b(y, x) 的性質存在。在本中我們要探討Tn 有k 個強勢王的存在性與唯一性。研究結果顯示，在Tn 中可存在任意k 個點的強勢王，1 ≦ k ≦ n，但須排除下面的例外情形：當n 為奇數時，不存在k = n - 1 個強勢王，或是當n 為偶數時，不存在k = n 個強勢王。另外在唯一性的研究方面；若不存在具有相同點數的競賽圖出現相同個數的強勢王，就稱此競賽圖具有唯一性。我們的研究結果可完全決定哪些競賽圖具備唯一性的條件。本文更得出在得分向量給定後，強勢王的最多與最少個數的界線為何。

本文的另一個主題是競賽圖所形成的『交換圖』。所謂交換圖是一個無向圖，這個圖形
中的點是一個競賽圖（即是給定得分序列後所產生的競賽圖），這個圖形的邊則是一種轉換關係（即是兩個競賽圖若能透過反轉圖形中任意三個點的迴圈而得到彼此，則交換圖中的兩點就形成一條邊）。本文將證明在特定得分序列 S = (1, 1, 2, . . . , n-2, n-2) 下所形成的交換圖是個超立方體圖。並且我們更證明在長度為n 的得分序列中只有這個得分序列所形成的交換圖是超立方體圖。除此之外，我們也研究雙分割競賽圖的交換圖，這個研究是建立在學者Bagga et al. [6] 過去研究特定雙分割競賽圖的結果；即某些得分序列可建構唯一交換圖的基礎上。針對這些可唯一建構的得分序列，我們將討論它所形成之交換圖的某些特性並建立公式來計算該圖形中點的個數及圖形上每個點的連結數。

最後一個主題是『王集合』。因為競賽圖中『王』的性質無法在一般有向圖上成立，例
如：一個競賽圖一定有個王，或一定沒有兩個王的性質，在一般有向圖中不一定成立。因此學者Bowser and Cable [19] 提出王集合的概念，這個概念與Chvatal and Lovasz [ 26] 稍早提出半核心的概念相似。所謂『王集合』是有向圖的一個子集合，在有向圖中的每一點（不在王集合中）都要被王集合中的點打敗，並且王集合中的各點均要不相連。本文將針對特定有向圖（具有均等數目腳的毛毛蟲有向圖）給一個計算方法來計算其王集合的個數。

Abstract
A tournament Tn is a complete oriented simple graph with n vertices, in which every pair of vertices is joined by exactly one arc. If the arc joining vertices x and y is directed from x to y, then x is said to dominate y and is denoted by x → y. The score of a vertex x is the number of vertices dominated by x in Tn. The score vector of Tn is the list of scores of vertices of Tn in a nondecreasing order.

A king x in a tournament Tn is a vertex who dominates any other vertex y directly or indirectly through a third vertex z (i.e., x → z and z → y). For x, y ? Tn, let b(x, y) denote the number of third vertices through which x dominates y indirectly. A vertex x is said to be a strong king if the following condition is fulfilled: b(x, y) > b(y, x) whenever y → x. In this dissertation, we determine whether there exists a tournament Tn with exactly k strong kings where 1 ≦ j ≦ n. A result shows that the answer is affirmative with the following exceptions: k = n - 1 when n is odd, and k = n when n is even. On the other hand, we further determine the uniqueness of tournaments, where a tournament is said to be unique if no other tournament with the same number of vertices (barring isomorphic ones) shares the same number of strong kings. As a result, we can completely determine the uniqueness of tournaments. Moreover, we propose an upper bound and a lower bound on the number of strong kings in tournaments under a score vector is given.

Next, we deal with the topic on interchange graphs. Let T (S) be the collection of tournaments that realize a given score vector S. A Δ-interchange is a transformation which reverses the directions of the arcs in a 3-cycle of a digraph. An interchange graph is an undirected graph whose vertices are the tournaments in T (S) and an edge joins two vertices (tournaments) if they can be transformed to each other by a Δ-interchange. In this dissertation, we show that a set of speci#c score vectors of tournaments, said S = (1, 1, 2, . . . , n - 2, n - 2), whose corresponding interchange graphs form a class of graphs called hypercubes. Moreover, we also present some properties of an interchange graph of bipartite tournaments. Based on a list of score vectors provided by Bagga et al. [6] for completely determining the uniquely realizable, we derive formulae for computing the regularity of regular interchange graphs of bipartite tournaments.

Finally, we study the topic of king sets. Landau [53] gave a result that implies that every tournament has at least a king. Maurer [65] proved that every tournament without a source has at least three kings. Neither of these results can be extended to arbitrary digraphs. Hence, Bowser and Cable [19] generalized the notion of kings to that of king sets which can be applied to arbitrary digraphs. In fact, the concept of king sets is the same idea of semi-kernel that was #rst introduced by Chvatal and Lovasz [26]. In this
dissertation, we derive formulae for counting the number of king sets of digraphs whose underlying graphs are caterpillars with regular legs.

Reference
[1] M. Aigner, Uses of the Diagram Lattice. Mitteil. Mathem. Sem. Giessen (Coxeter Festschrift). 163 (1984) 61-77.
[2] M. Aigner and E. Triesch, Realizability and Uniqueness in Graphs. Discrete Mathematics 136 (1994) 3-20.
[3] B. Alspach and K. B. Reid, Degree frequencies in digraphs and tournaments. Journal of Graph Theory 2 (1978) 241-249.
[4] P. Avery, Condition for a tournament score sequence to be simple. Journal of Graph Theory 4 (1980) 157-164.
[5] L. Babai and W. Imrich, Tournaments with Given Automorphism Group. Aequationes Mathematics 19 (1979) 232-244.
[6] K.S. Bagga, L.W. Beineke, and F. Wayne, Uniquely realizable score lists in bipartite tournaments, Czechoslovak Mathematical Journal, 37 (1987) 323–333.
[7] K.S. Bagga, L.W. Beineke, and F. Harary, Two Problems on Coloring Tournaments. Vishrva Internat. Journal of Graph Theory 1 (1992) 83-94.
[8] C. M. Bang and H. Jr. Sharp, An Elementary Proof of Moon’s Theorem on Generalized Tournaments. Journal of Combinatorial Theory, Series B 22 (1977) 299-301.
[9] C. M. Bang and H. Jr. Sharp, Score Vectors of Tournaments. Journal of Combinatorial Theory, Series B 26 (1979) 81-84.
[10] J. Bang-Jensen, Locally Semi-complete Digraphs: a Generalization of Tournaments. Journal of Graph Theory 14 (1990) 371-390.
[11] J. Bang-Jensen, On the Structure of Locally Semi-complete Digraphs. Discrete Mathematics 100 (1992) 243-265.
[12] J. Bang-Jensen and J. Huang, In-tournament Digraphs. Journal of Combinatorial Theory, Series B 59 (1993) 267-287.
[13] E. Barbut and Bialostocki, A Generalization of Rotational Tournaments. Discrete Mathematics 76 (1989) 81-87.
[14] E. Barbut and Bialostocki, Research Problem 135. Discrete Mathematics 88 (1991) 105-107.
[15] L.W. Beineke, A Tour through Tournaments or Bipartite and Ordinary Tournaments: a comparative survey. In Combinatorics; Swansea, 1981. London Mathematic Soc. Lecture Notes 52. Cambridge Univ. Press, Cambridge, 1981.
[16] L.W. Beineke and K. S. Bagga, On Superstrong Tournaments and Their Scores. In Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985. New York Acad. Sci. 1989. 30-39.
[17] L.W. Beineke and F. Harary, The Maximum number of Strongly Connected Subtournaments. Canad. Math. Bull. 8 (1965) 491-498.
[18] L.W. Beineke and J.W. Moon, “On bipartite tournaments and scores,” in: Proceedings of the Fourth International Conference on the Theory and Applications of Graphs (G. Chartrand et al. Ed.), John Wiley, 1981, pp. 55-71.
[19] S. E. Bowser and C. A. Cable, Digraphs with unique king sets, Discrete Mathematics 305 (2005) 347-349.
[20] S. E. Bowser and C. A. Cable, King sets for paths, cycles, and wheels, manuscript, (2007).
[21] A. Brauer, I. C. Gentry and K. Shaw, A New Proof of a Theorem by H. G. Landau on Tournament Matrices. Journal of Combinatorial Theory, Series A 5 (1968) 289-292.
[22] E. Brown and K. B. Reid, Doubly Regular Tournaments are Equivalent to Skew-Hadamard Matrices. Journal of Combinatorial Theory, Series A 13 (1972) 332-338.
[23] R.A. Brualdi and Q. Li, “The Interchange Graph of Tournaments with the Same Score Vector,” Progress in graph theory (J.A. Bondy and U.S.R. Murty, Eds.), Academic Press (1984) 128–151.
[24] P. Camion, Chemins et Circuits Hamiltoniens des Graphes Complets. C. R. Acad. Sci. Paris 249 (1959) 2151-2152.
[25] H. Chen, A. J. Schwenk and P. Erd?os, Tournaments that Share Several Common Moments with Their Complements. Bull. Inst. Combin. Appl. 4 (1992) 65-89.
[26] V. Chv?atal and L. Lov?asz, Every directed graph has a semi-kernel, in Hypergraph Seminar, Lecture Notes in Math. 441, Springer-Verlag, Berlin, 1974, p.175.
[27] M. Danut, A Note on Strong Tournaments. Rad. Mat. 3 (1987) 281-285.
[28] D. C. Fisher, J. R. Lundgren, S. K. Merz and K. B. Reid, The Domination and Competition Graphs of a Tournament. Journal of Graph Theory 29 (1998) 103-110.
[29] D. C. Fisher, J. R. Lundgren, S. K. Merz and K. B. Reid, Domination Graphs of Tournaments and Digraphs. Congressus Numerantium 108 (1995) 97-107.
[30] D. C. Fisher and J. Ryan, Tournament Games and Positive Tournaments. Journal of Graph Theory 19 (1995) 217-236.
[31] D. R. Fulkerson, Zero-one Matrices with Zero Trace. Paci"c Journal of Mathematics 10 (1960) 831-836.
[32] D.R. Fulkerson, Upsets in Round Robin Tournaments, Canad. J. Math., 17 (1965), pp. 975–969
[33] S. V. Gervacio, Score Sequence: Lexicographic Enumeration and Tournament Construction. Proceedings of the First Japan Conference on Graph Theory and Applications, Hakone, 1986. Discrete Mathematics 72 (1988) 151-155.
[34] S. V. Gervacio, Construction of Tournaments with a Given Score Sequence. Southeast Asian Bull. Math. 17 (1993) 151-155.
[35] Peter M. Gibson, A Bound for the Number of Tournaments with Speci#ed Scores, Journal of Combinatorial Theory, Series B 36 (1984) 240-243.
[36] W. D. Goddard, G. Kubicki, O. R. Oellermann and S. Tian, On Multipartite Tournaments. Journal of Graph Theory, Series B 52 (1991) 284-300.
[37] G. M. Gutin, The Radii of N-partite Tournaments. Mat. Zametki 40 (1986) 414-417.
[38] G. M. Gutin, Cycles and Paths in Semicomplete Multipartite Digraphs, Theorems and Algorithms: a survey. Journal of Graph Theory 19 (1995) 481-505.
[39] M. Hager, On Score Set for Tournaments. Discrete Mathematics 58 (1986) 25-34.
[40] F. Harary and L. Moser, The Theory of Round Robin Tournaments. Am. Math. Mon. 72 (1966) 231-246.
[41] T. Y. Ho and J. M. Chang, Sorting a Sequence of Strong Kings in a Tournament, Information Processing Letters, 87 (2003) 317-320.
[42] W. Honghui and L. Qiao, On the Number of Tournaments with Prescribed Score Vector. Discrete Mathematics 61 (1986) 213-219.
[43] J. Huang and W. Li, Toppling Kings in a Tournament by Introducing New Kings. Journal of Graph Theory 11 (1987) 7-11.
[44] M. Jacobson, E. Kubicka and G. Kubicki, Vertex Rotation Number for Tournaments. Congressus Numerantium 82 (1991) 201-210.
[45] R. Kannan, P. Tetali, S. Vempala. Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Random Struct. Algorithm, 14, (1999), pp. 293-308.
[46] S. Kirkland On the Minimum Perron Value for an Irreducible Tournament Matrix Linear Algebra and Its Applications 244 (1996) 277-304.
[47] K. M. Koh and B. P. Tan, Multipartite Tournaments having Exactly Four 4-kings. In Combinatorics, Graph Theory, Algorithms and Applications (Beijing, 1993), World Sci. Publ., River Edge, NJ (1994) 125-136.
[48] K. M. Koh and B. P. Tan, Multipartite Tournaments with Prescribed Sets of Kings. Bulletin of the Institute of Combinatorics and Its Applications 13 (1995) 15-22.
[49] K. M. Koh and B. P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings. Discrete Mathematics 154 (1996) 281-287.
[50] K. M. Koh and B. P. Tan, The number of kings in a multipartite tournament. Discrete Mathematics 167 (1997) 411-418.
[51] H. G. Landau, On dominance relations and the structure of animal societies. I: E!ect of inherent characteristics, Bulletin of Mathematical Biophysics, 13 (1951) 1-19.
[52] H. G. Landau, On dominance relations and the structure of animal societies II: Some e!ects of possible social factors, Bulletin of Mathematical Biophysics, 13 (1951) 245-262.
[53] H. G. Landau, On dominance relations and the structure of animal societies, III: the condition for a score structure, Bulletin of Mathematical Biophysics, 15 (1953) 143–148.
[54] S. J. Li, Score Vectors of 3-strong Tournaments. Acta Math. Sinica 34 (1991) 226-233.
[55] S. J. Li, Non-h-strong Tournaments and Their Score Vectors. Journal Math. Res. Exposition 11 (1991) 465-468.
[56] S. J. Li and G. X. Huang, Score Vectors of Tournaments. Graph Theory and Its Applications: East and West (Jinan, 1986). New York Acad. Sci. (1989) 323-327.
[57] S. J. Li and G. X. Huang, The Pairs of Score Lists of T-reducible Bipartite Tournaments. Acta Math. Appl. Sinica 10 (1987) 418-427.
[58] S. J. Li and G. X. Huang, Kotzig’s Problem for Multipartite Tournaments. Adv. in Math. 17 (1988) 398-402.
[59] S. J. Li and G. X. Huang, Score Vectors of [(n-1)/2]-strong n-tournaments. Chinese Ann. Math. Series A 9 (1988) 665-670.
[60] S. J. Li and G. X. Huang, Score Vectors of T-reducible Tournaments. Journal Math. Res. Exposition 8 (1988) 521-525.
[61] Q. Li, Some Results and Problems in Graph Theory. Graph theory and its applications: East and West (Jinan, 1986). New York Acad. Sci., (1989) 336-343.
[62] Y. C. Lin, G. X. Huang and J. S. Li, Score Vectors of Kotzig Tournaments. Journal of Combinatorial Theory Series B 43 (1987) 328-336.
[63] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Applications. Academic Press, New York (1979).
[64] S. Marshall, On the Existence of k-tournaments with Given Automorphism Group. Discrete Mathematics 152 (1996) 259-268.
[65] S. B, Maurer, The king chicken theorems, Mathematics Magazine 53 (1980) 67-80.
[66] Lisa McShine. Random Sampling of Labeled Tournaments. The Electronic Journal of Combinatorics 7(1) (2000)
[67] J. W. Moon, On the Score Sequence of an n-partite Tournament. Can. Math. Bull. 5 (1962) 51-58.
[68] J. W. Moon, On some combinatorial and probabilistic aspects of bipartite graphs. Ph. D. thesis, University of Alberta, Edmonton, 1962.
[69] J. W. Moon, Solution to problem 463, Mathematics Magazine 35 (1962) 189.
[70] J. W. Moon, An Extension of Landau’s Theorem on Tournaments. Paci"c Journal Mathematics 13 (1963) 1343-1345.
[71] J. W. Moon, Tournaments with given automorphism group. Canad. J. Math. 16 (1964) 485-489.
[72] J. W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York (1968).
[73] J. W. Moon, Tournaments with a Given Number of Kings and Serfs. Congressus Numerantium 96 (1993) 27-32.
[74] J. W. Moon, Uncovered Nodes and 3-cycle in Tournaments. Australasian Journal Combinatorics 7 (1993) 157-173.
[75] L. Moser, Asymptotics of Tournament Scores. Combinatorics Proceedings of the Symposium in Pure Math. Vol. XIX, at U.C.L.A., March 21-22, 1968. Am. Math. Soc., (1971) 165-166.
[76] V. Petrovic, On Bipartite Score Sets. Univ. u Novom Sadu Zb. Rad. Prirod. Mat. Fak. Ser. Mat. 13 (1983) 297-303.
[77] V. Petrovic, On Frequency Sets of Bipartite Tournaments. Graph Theory
(Dubrovnik, 1985) Univ. Novi Sad (1986) 173-178.
[78] V. Petrovic, Degree Frequencies in 3-partite Tournaments. Univ. u Novom Sadu Zb. Rad. Prirod. Mat. Fak. Ser. Mat. 17 (1987) 217-228.
[79] V. Petrovic, Some Particular Degree Frequencies in k-partite Tournaments. Graph Theory (Novi Sad, 1987), Univ. Novi Sad (1989) 106-112.
[80] V. Petrovic and C. Thomassen, Kings in k-partite Tournaments. Discrete Mathematics 98 (1991) 237-238.
[81] R. Rado, Theorems on Linear Combinatorial Topology and General Measure. Ann. of Math. 44 (1943) 228-270.
[82] K. B. Reid, Score Sets for Tournaments. Congressus Numerantium 21 (1978) 607- 618.
[83] K. B. Reid, Tournaments with Prescribed Numbers of Kings and Serfs. Congressus Numerantium 29 (1980) 809-826.
[84] K. B. Reid, Every Vertex a King. Discrete Mathematics 38 (1982) 93-98.
[85] K. B. Reid, Three Problems on Tournaments. Graph Theory and Its Applications: East and West, Annals of the New York Academy of Sciences 576 (1989) 466-473.
[86] K. B. Reid, Majority Tournaments: Sincere and Sophisticated Voting Decisions under Amendment Procedure. Math. Social Sciences 21 (1991) 1-19.
[87] K. B. Reid, The Relationship Between Two Algorithms for Decisions via Sophisticated Majority Voting with an Agenda. Discrete Applied Mathematics 31 (1991) 23-28.
[88] K. B. Reid, Tournaments: scores, kings, generalizations and special topics. Congressus Numerantium 115 (1996) 171-211.
[89] K. B. Reid, “Tournaments,” In: Jonathan L. Gross and Jay Yellan, Handbook of Graph Theory, CRC Press, (2004), pp. 156–184.
[90] K. B. Reid and L. W. Beineke, “Tournaments,” In: L. W. Beineke and R. Wilson, (Eds.), Selected Topics in Graph Theory, Academic Press, London (1978) 169-204.
[91] A. Richard, Brualdi, Upsets in Round Robin Tournaments. Journal of Combinatorial Theory, Series B 35 (1983) 62-77.
[92] J. Riordan, The Number of Score Sequences in Tournaments. Journal of Combinatorial Theory 5 (1968) 87-89.
[93] J. Riordan, Erratum: The Number of Score Sequences in Tournaments. Journal of Combinatorial Theory 6 (1969) 226.
[94] H.J. Ryser, Combinatorial Properties of Matrices of 0’s and 1’s. Canad. J. Math. 9 (1957) 371-377.
[95] H.J. Ryser, Matrices of zeros and ones in combinatorial mathematics. In: Recent Advances in Matrix Theory, ed. H. Schneider (University of Wisconsin Press, Madison) (1964) 103-124.
[96] Y. Saad and M. H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 37 (1988) 867-872.
[97] J. Y. Shao, The Connectivity of the Interchange Graph of the Class of Tournaments with a Fixed Score Vector. Tongji Daxue Xuebao 15 (1987) 239-242.
[98] D. Soroker, Optimal Parallel Construction of Prescribed Tournaments. Discrete Applied Mathematics 29 (1990) 113-125.
[99] M. R. Sridharan and Merajuddin, Some Properties of Score Sequences of Tournaments. Combinatorics and Applications (Calcutta, 1982). Indian Statist. Inst. (1984) 329-333.
[100] C. Thomassen, Landau’s Characterization of Tournament Score Sequences. The Theory and Applications of Graphs (Kalamazoo, Mich., 1980). John Wiley & Sons (1981) 589-591.
[101] R. Tosic, Degree Frequencies in k-partite Tournaments. Graph Theory (Novi Sad, 1987). Univ. Novi Sad (1987) 123-126.
[102] A. Asti?e-Vidal, V. Dugat and Z. Tuza, Construction of Non-isomorphic Regular Tournaments. Combinatorics ’90 (edited by A. Bichara et. al.). Annals of Discrete Mathematics 52 (1992) 11-23.
[103] H. H. Wan and Q. Li, On the Number of Tournaments with Prescribed Score Vector. Discrete Mathematics 61 (1986) 213-219.
[104] E. T. Wang and Z. Shan, An Application of Number Theory to Tournaments. Graph Theory, Combinatorics, Algorithms, and Application (San Francisco, CA, 1989) SIAM (1991) 581-587.
[105] K. Wayland, Bipartite Score Sets. Canad. Math. Bull. 26 (1983) 273-279.
[106] K. Wayland, Getting Your Chickens Elected. Congressus Numerantium 45 (1984) 311-318.
[107] D. Wayne, Goddard On Multipartite Tournaments. Journal of Combinatorial Theory, Series B 52 (1991) 284-300.
[108] K. J. Winston and D. J. Kleitman, On the Asymptotic Number of Tournament Score Sequences. Journal of Combinatorial Theory, Series A 35 (1983) 208-230.
[109] Z. S. Wu, Some Results on the Kings in a Tournament. Acta. Math. Appl. Sinica 10 (1987) 284-288.
[110] T. X. Yao, Reid’s Conjecture on Score Sets in Tournaments (in Chinese). Kexue Tongbao 33 (1988) 481-484.
[111] T. X. Yao, On Reid Conjecture of Score Sets for Tournaments. Chinese Sci. Bull. 34 (1989) 804-808.
[112] T. X. Yao, Score Sets of Bipartite Tournaments. Nanjing Daxue Xuebao Ziran Kexue Ban 26 (1990) 19-23.