首页    期刊浏览 2024年12月13日 星期五
登录注册

文章基本信息

  • 标题:Rainbow Cycles in Flip Graphs
  • 作者:Stefan Felsner ; Linda Kleist ; Torsten M{\"u}tze
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:99
  • 页码:38:1-38:14
  • DOI:10.4230/LIPIcs.SoCG.2018.38
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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 spanning trees on an arbitrary set of n points, and the flip graph of non-crossing perfect matchings on a set of n points in convex position. In addition, we consider two flip graphs on classes of non-geometric 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 non-existence of rainbow cycles for different values of r, n and k.
  • 关键词:flip graph; cycle; rainbow; Gray code; triangulation; spanning tree; matching; permutation; subset; combination
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有