{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:62595"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:62595","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Local tournaments and in-tournaments","abstract":"A digraph without loops, multiple arcs and cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In claiming adjacency only for vertices that have a common out-neighbor, this class can be further generalized to the class of in-tournaments. Hence local tournaments and in-tournaments are generalizations of tournaments in such a way that the general adjacency of vertices is transferred to only those pairs of vertices that share a local property. In this thesis we study the path and cycle structure of local tournaments and in-tournaments and the related topic of vertex deletion. The required terminology and notation as well as the basic structural properties of local tournaments and in-tournaments are established in Chapter 1. The remaining part of this thesis is subdivided in three parts. In the first part consisting of Chapters 2 to 4 we investigate the path structure of local tournaments and in-tournaments. The first problem we deal with in Chapter 2 is to develop the structure necessary for a local tournament to be not arc-traceable, i.e. to contain an arc that does not belong to a Hamiltonian path. Using this structure we give various sufficient criteria for a local tournament to be arc-traceable. Our results extend those of Busch, and Busch, Jacobson and Reid for tournaments. In the next two chapters - Chapters 3 and 4 - we focus on shorter paths in local tournaments and in-tournaments. We study and confirm a conjecture of Volkmann and, subsequently, consider variations of Volkmann's problem. The second part of this thesis consists of two chapters in which we investigate the following problem: How many non-separating vertices has a strongly connected local tournament or in-tournament in terms of minimum vertex degree? In Chapter 5 we generalize results of Kotani for tournaments and of Meierling and Volkmann for local tournaments. The topic of Chapter 6 is the problem of vertex deletion, where we ask for the existence of two distinct vertices in a strongly connected local tournament whose removal preserves the strong connectivity of the digraph. We characterize all local tournaments with exactly two such vertices thereby generalizing a result of Las Vergnas for tournaments. The third part of this thesis is devoted to the cycle structure of local tournaments and in-tournaments. A reformulation of the results of Chapter 6 shows that we characterized all local tournaments with exactly two cycles of length order minus one. Using a special parameter, the quasi-girth of a local tournament, we investigate in Chapter 7 how many cycles of a given length, a strongly connected local tournament has at the least. This problem has already been studied and solved completely by Moon, and Las Vergnas for tournaments and our results generalize those of Las Vergnas. The interesting problem of complementary cycles in strongly connected local tournaments is investigated in Chapter 8. In 1996 Guo and Volkmann solved the question whether a 2-connected local tournament has complementary cycles in characterizing the exceptional digraphs. This result was generalized and extended in various forms. For example, Meierling and Volkmann characterized all 2-connected in-tournaments that are not cycle complementary. In this chapter we investigate the structure of strongly connected, but not 2-connected, local tournaments that are not cycle complementary. As applications we present sufficient criteria for a strongly connected local tournament to have k vertex disjoint cycles that span its vertex set. Our results extend and generalize those of Li and Shu for tournaments. In the last chapter we consider extendable cycles in strongly connected in-tournaments. In 1989 this property was introduced by Hendry in the context of general digraphs and subsequently studied by Tewes and Volkmann for in-tournaments. We solve a conjecture of Tewes and Volkmann in the affirmative.","abstract_html":"A digraph without loops, multiple arcs and cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In claiming adjacency only for vertices that have a common out-neighbor, this class can be further generalized to the class of in-tournaments. Hence local tournaments and in-tournaments are generalizations of tournaments in such a way that the general adjacency of vertices is transferred to only those pairs of vertices that share a local property. In this thesis we study the path and cycle structure of local tournaments and in-tournaments and the related topic of vertex deletion. The required terminology and notation as well as the basic structural properties of local tournaments and in-tournaments are established in Chapter 1. The remaining part of this thesis is subdivided in three parts. In the first part consisting of Chapters 2 to 4 we investigate the path structure of local tournaments and in-tournaments. The first problem we deal with in Chapter 2 is to develop the structure necessary for a local tournament to be not arc-traceable, i.e. to contain an arc that does not belong to a Hamiltonian path. Using this structure we give various sufficient criteria for a local tournament to be arc-traceable. Our results extend those of Busch, and Busch, Jacobson and Reid for tournaments. In the next two chapters - Chapters 3 and 4 - we focus on shorter paths in local tournaments and in-tournaments. We study and confirm a conjecture of Volkmann and, subsequently, consider variations of Volkmann&#x27;s problem. The second part of this thesis consists of two chapters in which we investigate the following problem: How many non-separating vertices has a strongly connected local tournament or in-tournament in terms of minimum vertex degree? In Chapter 5 we generalize results of Kotani for tournaments and of Meierling and Volkmann for local tournaments. The topic of Chapter 6 is the problem of vertex deletion, where we ask for the existence of two distinct vertices in a strongly connected local tournament whose removal preserves the strong connectivity of the digraph. We characterize all local tournaments with exactly two such vertices thereby generalizing a result of Las Vergnas for tournaments. The third part of this thesis is devoted to the cycle structure of local tournaments and in-tournaments. A reformulation of the results of Chapter 6 shows that we characterized all local tournaments with exactly two cycles of length order minus one. Using a special parameter, the quasi-girth of a local tournament, we investigate in Chapter 7 how many cycles of a given length, a strongly connected local tournament has at the least. This problem has already been studied and solved completely by Moon, and Las Vergnas for tournaments and our results generalize those of Las Vergnas. The interesting problem of complementary cycles in strongly connected local tournaments is investigated in Chapter 8. In 1996 Guo and Volkmann solved the question whether a 2-connected local tournament has complementary cycles in characterizing the exceptional digraphs. This result was generalized and extended in various forms. For example, Meierling and Volkmann characterized all 2-connected in-tournaments that are not cycle complementary. In this chapter we investigate the structure of strongly connected, but not 2-connected, local tournaments that are not cycle complementary. As applications we present sufficient criteria for a strongly connected local tournament to have k vertex disjoint cycles that span its vertex set. Our results extend and generalize those of Li and Shu for tournaments. In the last chapter we consider extendable cycles in strongly connected in-tournaments. In 1989 this property was introduced by Hendry in the context of general digraphs and subsequently studied by Tewes and Volkmann for in-tournaments. We solve a conjecture of Tewes and Volkmann in the affirmative.","abstract_has_math":false,"creators":["Meierling, Dirk"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Volkmann, Lutz"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-30T19:43:28Z","subjects":["info:eu-repo/classification/ddc/510","Turnier <Mathematik>","Mathematik","graph theory","digraph","local tournament","in-tournament"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124154%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124154%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124154%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/62595","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Volkmann, Lutz"]},{"key":"dc:creator","label":"Author","values":["Meierling, Dirk"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-21199"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/510","Turnier <Mathematik>","Mathematik","graph theory","digraph","local tournament","in-tournament"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/62595","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124154%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A digraph without loops, multiple arcs and cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In claiming adjacency only for vertices that have a common out-neighbor, this class can be further generalized to the class of in-tournaments. Hence local tournaments and in-tournaments are generalizations of tournaments in such a way that the general adjacency of vertices is transferred to only those pairs of vertices that share a local property. In this thesis we study the path and cycle structure of local tournaments and in-tournaments and the related topic of vertex deletion. The required terminology and notation as well as the basic structural properties of local tournaments and in-tournaments are established in Chapter 1. The remaining part of this thesis is subdivided in three parts. In the first part consisting of Chapters 2 to 4 we investigate the path structure of local tournaments and in-tournaments. The first problem we deal with in Chapter 2 is to develop the structure necessary for a local tournament to be not arc-traceable, i.e. to contain an arc that does not belong to a Hamiltonian path. Using this structure we give various sufficient criteria for a local tournament to be arc-traceable. Our results extend those of Busch, and Busch, Jacobson and Reid for tournaments. In the next two chapters - Chapters 3 and 4 - we focus on shorter paths in local tournaments and in-tournaments. We study and confirm a conjecture of Volkmann and, subsequently, consider variations of Volkmann's problem. The second part of this thesis consists of two chapters in which we investigate the following problem: How many non-separating vertices has a strongly connected local tournament or in-tournament in terms of minimum vertex degree? In Chapter 5 we generalize results of Kotani for tournaments and of Meierling and Volkmann for local tournaments. The topic of Chapter 6 is the problem of vertex deletion, where we ask for the existence of two distinct vertices in a strongly connected local tournament whose removal preserves the strong connectivity of the digraph. We characterize all local tournaments with exactly two such vertices thereby generalizing a result of Las Vergnas for tournaments. The third part of this thesis is devoted to the cycle structure of local tournaments and in-tournaments. A reformulation of the results of Chapter 6 shows that we characterized all local tournaments with exactly two cycles of length order minus one. Using a special parameter, the quasi-girth of a local tournament, we investigate in Chapter 7 how many cycles of a given length, a strongly connected local tournament has at the least. This problem has already been studied and solved completely by Moon, and Las Vergnas for tournaments and our results generalize those of Las Vergnas. The interesting problem of complementary cycles in strongly connected local tournaments is investigated in Chapter 8. In 1996 Guo and Volkmann solved the question whether a 2-connected local tournament has complementary cycles in characterizing the exceptional digraphs. This result was generalized and extended in various forms. For example, Meierling and Volkmann characterized all 2-connected in-tournaments that are not cycle complementary. In this chapter we investigate the structure of strongly connected, but not 2-connected, local tournaments that are not cycle complementary. As applications we present sufficient criteria for a strongly connected local tournament to have k vertex disjoint cycles that span its vertex set. Our results extend and generalize those of Li and Shu for tournaments. In the last chapter we consider extendable cycles in strongly connected in-tournaments. In 1989 this property was introduced by Hendry in the context of general digraphs and subsequently studied by Tewes and Volkmann for in-tournaments. We solve a conjecture of Tewes and Volkmann in the affirmative."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University XII, 160 S. : graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"]},{"key":"dc:title","label":"Title","values":["Local tournaments and in-tournaments"]}]}],"canonical_facts":{"dc:contributor":["Volkmann, Lutz"],"dc:coverage":["DE"],"dc:creator":["Meierling, Dirk"],"dc:date":["2007"],"dc:description":["A digraph without loops, multiple arcs and cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In claiming adjacency only for vertices that have a common out-neighbor, this class can be further generalized to the class of in-tournaments. Hence local tournaments and in-tournaments are generalizations of tournaments in such a way that the general adjacency of vertices is transferred to only those pairs of vertices that share a local property. In this thesis we study the path and cycle structure of local tournaments and in-tournaments and the related topic of vertex deletion. The required terminology and notation as well as the basic structural properties of local tournaments and in-tournaments are established in Chapter 1. The remaining part of this thesis is subdivided in three parts. In the first part consisting of Chapters 2 to 4 we investigate the path structure of local tournaments and in-tournaments. The first problem we deal with in Chapter 2 is to develop the structure necessary for a local tournament to be not arc-traceable, i.e. to contain an arc that does not belong to a Hamiltonian path. Using this structure we give various sufficient criteria for a local tournament to be arc-traceable. Our results extend those of Busch, and Busch, Jacobson and Reid for tournaments. In the next two chapters - Chapters 3 and 4 - we focus on shorter paths in local tournaments and in-tournaments. We study and confirm a conjecture of Volkmann and, subsequently, consider variations of Volkmann's problem. The second part of this thesis consists of two chapters in which we investigate the following problem: How many non-separating vertices has a strongly connected local tournament or in-tournament in terms of minimum vertex degree? In Chapter 5 we generalize results of Kotani for tournaments and of Meierling and Volkmann for local tournaments. The topic of Chapter 6 is the problem of vertex deletion, where we ask for the existence of two distinct vertices in a strongly connected local tournament whose removal preserves the strong connectivity of the digraph. We characterize all local tournaments with exactly two such vertices thereby generalizing a result of Las Vergnas for tournaments. The third part of this thesis is devoted to the cycle structure of local tournaments and in-tournaments. A reformulation of the results of Chapter 6 shows that we characterized all local tournaments with exactly two cycles of length order minus one. Using a special parameter, the quasi-girth of a local tournament, we investigate in Chapter 7 how many cycles of a given length, a strongly connected local tournament has at the least. This problem has already been studied and solved completely by Moon, and Las Vergnas for tournaments and our results generalize those of Las Vergnas. The interesting problem of complementary cycles in strongly connected local tournaments is investigated in Chapter 8. In 1996 Guo and Volkmann solved the question whether a 2-connected local tournament has complementary cycles in characterizing the exceptional digraphs. This result was generalized and extended in various forms. For example, Meierling and Volkmann characterized all 2-connected in-tournaments that are not cycle complementary. In this chapter we investigate the structure of strongly connected, but not 2-connected, local tournaments that are not cycle complementary. As applications we present sufficient criteria for a strongly connected local tournament to have k vertex disjoint cycles that span its vertex set. Our results extend and generalize those of Li and Shu for tournaments. In the last chapter we consider extendable cycles in strongly connected in-tournaments. In 1989 this property was introduced by Hendry in the context of general digraphs and subsequently studied by Tewes and Volkmann for in-tournaments. We solve a conjecture of Tewes and Volkmann in the affirmative."],"dc:identifier":["https://publications.rwth-aachen.de/record/62595","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124154%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-21199"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University XII, 160 S. : graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"],"dc:subject":["info:eu-repo/classification/ddc/510","Turnier <Mathematik>","Mathematik","graph theory","digraph","local tournament","in-tournament"],"dc:title":["Local tournaments and in-tournaments"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:43:28Z"}