A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.
","abstract_html":"<p>A. Ádám conjectured that for any non-acyclic digraph <em>D</em>, there exists an arc whose reversal reduces the total number of cycles in <em>D</em>. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.</p>","abstract_has_math":false,"creators":["Salas, Claudio D"],"institution":null,"degree_name":"Master of Arts in Mathematics","degree_level":"Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Aikin, Jeremy"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-06-01T07:00:00Z","date_published":"2016-06-01T07:00:00Z","updated_at":"2026-07-24T01:53:00Z","subjects":["Ádám's Conjecture","Arc Reversal Problems","quasi-acyclic","arc-cycle transversal","reversal set","Discrete Mathematics and Combinatorics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarworks.lib.csusb.edu/etd/337","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Aikin, Jeremy"]},{"key":"dc:creator","label":"Author","values":["Salas, Claudio D"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2016-05-19T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Arts in Mathematics"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Ádám's Conjecture","Arc Reversal Problems","quasi-acyclic","arc-cycle transversal","reversal set","Discrete Mathematics and Combinatorics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarworks.lib.csusb.edu/etd/337"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.
"]},{"key":"dc:title","label":"Title","values":["Ádám's Conjecture and Arc Reversal Problems"]}]}],"canonical_facts":{"dc:contributor":["Aikin, Jeremy"],"dc:creator":["Salas, Claudio D"],"dc:date.available":["2016-05-19T07:00:00Z"],"dc:description.abstract":["A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.
"],"dc:identifier":["https://scholarworks.lib.csusb.edu/etd/337"],"dc:subject":["Ádám's Conjecture","Arc Reversal Problems","quasi-acyclic","arc-cycle transversal","reversal set","Discrete Mathematics and Combinatorics"],"dc:title":["Ádám's Conjecture and Arc Reversal Problems"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Arts in Mathematics"]},"updated_at":"2026-07-24T01:53:00Z"}