The number of bipartite tournaments with a unique given factor

✍ Scribed by Manoussakis Manolis; Manoussakis Yannis

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 571 KB
• Volume: 13
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190130311

✦ Synopsis

We give a recursive function in order to calculate the number of all nonisomorphic bipartite tournaments containing an unique hamiltonian cycle. Using this result we determine the number of all nonisomorphic bipartite tournaments that admit an unique factor isomorphic to a given l-diregular bipartite graph.

We determine the number, denoted by w, I, ,c,, of all nonisomorphic bipartite tournaments containing an unique factor isomorphic to vertex disjoint union of c p ~, L ~, cl, . . . , Cm (m z n, of lengths, respectively, cI, c2, . . . c, , ~L I I c, 2 6 and c, # c, , 1 5 i , j 5 m , i # j . In order to do that, we shall first study in Section 1 the special case m = 1 by following an idea originally exposed in [2]; using this result, we shall then study the general case m 2 2 in Section 2. Formally, we let B, = (X, , Y, , E ) denote a bipartite tournament on n vertices with partition ( X , , Y , ) , where IX,I = IY,l and 6 5 n = 2a. Then V ( B , ) (= X , U Y,) denotes the set of vertices and E(B,) denotes the set of arcs of B, . If x and y are vertices of B,, then we shall say that x dominates y if the arc (x, y ) is present. For x E B, , we define T-(x) and Tt(x) to be the sets of vcrtices of B, that, respectively, dominate and are dominated bj &e vertex X. The outdegree, indegree, and degree of a verteu-fi-defined as /Tt(x)l, lT-(x)l, /and II'-(x)( + Ir+(x)l(= a), r?%pt%tively, and are denoted d+(x), d -( x ) , and d(x), respectively. We -dial1 say that a vertex x of B, is large if dt(x) = a -1 (and hence d-(x) = 1). We say that two cycles are &€&rent if they have not all arcs in common. Furthem-, C: xl + y1 + -+ xp + yp + x , denotes a cycle of B, , where x, E X, znd y , E Y, , unless otherwise specified.