CEU Electronic Theses and Dissertations, 2015
| Author | Ergemlidze, Beka |
|---|---|
| Title | Characterizing of digraphs with every edge in a fixed number of cycles |
| Summary | About 40 years ago A. AdŽam described the structure of the digraphs with every vertex Ž being in at most two cycles. He provided constructive theorem for it and raised the problem: How to describe the digraphs with every edge at most in two cycles? Later Zelinka and Gy˝ori proved that Necklace is the only directed graph with the property that every edge is contained in exactly 2 directed cycles. Gy˝ori also provided both constructive and direct structure theorems of more general problem with every edge being in at most 2 directed cycles. He also described that if we know solution for every edge being in at most k cycles then we can easily characterize digraphs with every vertex in at most k + 1 cycles. In the present note, we give a characterization of directed graphs with the property that every edge is contained in exactly 3 directed cycles. We will also provide interesting examples for the digraphs with every edge in k of cycles for some higher k. This is a joint paper with my coursemate Abhishek Methuku and supervisor Ervin Gy˝ori. |
| Supervisor | Gyori Ervin |
| Department | Mathematics MSc |
| Full text | https://www.etd.ceu.edu/2015/ergemlidze_beka.pdf |
Visit the CEU Library.
© 2007-2021, Central European University