Rainbow cycles in flip graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10419957" target="_blank" >RIV/00216208:11320/20:10419957 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=noYFAmtzud" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=noYFAmtzud</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/18M1216456" target="_blank" >10.1137/18M1216456</a>
Alternative languages
Result language
angličtina
Original language name
Rainbow cycles in flip graphs
Original language description
The flip graph of triangulations has as vertices all triangulations of a convex n-gon and an edge between any two triangulations that differ in exactly one edge. An r-rainbow cycle in this graph is a cycle in which every inner edge of the triangulation appears exactly r times. This notion of a rainbow cycle extends in a natural way to other flip graphs. In this paper we investigate the existence of r-rainbow cycles for three different flip graphs on classes of geometric objects: the aforementioned flip graph of triangulations of a convex n-gon, the flip graph of plane trees on an arbitrary set of n points, and the flip graph of noncrossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of nongeometric objects: the flip graph of permutations of {1, 2, ..., n} and the flip graph of k-element subsets of {1, 2, ..., n}. In each of the five settings, we prove the existence and nonexistence of rainbow cycles for different values of r, n, and k.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-08554S" target="_blank" >GA19-08554S: Structures and algorithms in highly symmetric graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Volume of the periodical
34
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
39
Pages from-to
1-39
UT code for WoS article
000546886700001
EID of the result in the Scopus database
2-s2.0-85079770225