ISSN 2590-9770
The Art of Discrete and Applied Mathematics 2 (2019) #P1.07
https://doi.org/10.26493/2590-9770.1251.b76
(Also available at http://adam-journal.eu)
Parallelism of stable traces
Jernej Rus ∗
Abelium d.o.o., Kajuhova 90, 1000 Ljubljana, Slovenia
Received 18 May 2018, accepted 19 September 2018, published online 8 August 2019
Abstract
A parallel d-stable trace is a closed walk which traverses every edge of a graph exactly
twice in the same direction and for every vertex v, there is no subset X ⊆ N(v) with
1 ≤ |N | ≤ d such that every time the walk enters v from X , it also exits to a vertex in
X . In the past, d-stable traces were investigated as a mathematical model for an innovative
biotechnological procedure – self-assembling of polypeptide structures. Among other, it
was proven that graphs that admit parallel d-stable traces are precisely Eulerian graphs
with minimum degree strictly larger than d. In the present paper we give an alternative,
purely combinatorial proof of this result.
Keywords: Eulerian graph, parallel d-stable trace, nanostructure design, self-assembling, polypep-
tide.
Math. Subj. Class.: 05C45, 05C85, 94C15
∗The author is grateful to Sandi Klavžar and anonymous reviewers for several significant remarks and sug-
gestions which were of great help. The authors acknowledge the financial support from the Slovenian Research
Agency H2020 SME2 and the SPIRIT Slovenia - Public Agency for Entrepreneurship, Internationalization, Fore-
ign Investments and Technology - KKIPP.
E-mail address: jernej.rus@gmail.com (Jernej Rus)
cb This work is licensed under https://creativecommons.org/licenses/by/3.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 2 (2019) #P1.07
https://doi.org/10.26493/2590-9770.1251.b76
(Dostopno tudi na http://adam-journal.eu)
Paralelnost stabilnih obhodov
Jernej Rus ∗
Abelium d.o.o., Kajuhova 90, 1000 Ljubljana, Slovenia
Prejeto 18. maja 2018, sprejeto 19. septembra 2018, objavljeno na spletu 8. avgusta 2019
Povzetek
Paralelen d-stabilen obhod je sklenjen sprehod, ki vsako povezava grafa prečka natanko
dvakrat v isti smeri, pri tem pa za vsako vozlišče v velja, da ne obstaja taka podmnožica
njegovih sosedov X ⊆ N(v), 1 ≤ |X| ≤ d, da vsakič, ko sprehod pride v v iz vozlišča
v X , tudi zapusti v v smeri proti vozlišču v X . V preteklosti so bili d-stabilni obhodi,
kot matematični model za nove in inovativne biotehnološke raziskave, že raziskani. Med
drugim so bili grafi, ki vsebujejo paralalne d-stabilne obhode karakterizirani kot Eulerjevi
grafi z minimalno stopnjo δ > d. V pričujočem članku je podan alternativni (kombina-
torični) dokaz tega rezultata.
Ključne besede: Eulerjev graf, paralelni d-stabilni obhodi, oblikovanje nanostruktur, samosestavlji-
vost, polipeptidi.
Math. Subj. Class.: 05C45, 05C85, 94C15
∗Avtor je hvaležen Sandiju Klavžarju in anonimnim recenzentom za vse pripombe, ki so mu bile v ve-
liko pomoč. Prav tako avtor hvaležno priznava podporo s strani Slovenian Research Agency H2020 SME2 in
SPIRIT Slovenia - Public Agency for Entrepreneurship, Internationalization, Foreign Investments and Technol-
ogy - KKIPP.
E-poštni naslov: jernej.rus@gmail.com (Jernej Rus)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/3.0/