Triangle-different Hamiltonian paths
Triangle-different Hamiltonian paths
复制标题
三角形不同哈密顿路径
DOI：
10.1016/j.jctb.2017.09.003
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Daniel Soltész
中科院分区：
文献类型：
--
作者：
I. Kovács;Daniel Soltész
设G为固定图。如果在 n 个顶点上长度为 n−1 的两条路径（哈密尔顿路径）在它们的并集中存在与 G 同构的子图，则它们是 G 不同的。在本文中，我们证明了成对三角形不同哈密顿路径的最大数量等于地面集平衡二分的数量，回答了 Körner、Messuti 和 Simonyi 的问题。
Let G be a fixed graph. Two paths of length n− 1 on n vertices (Hamiltonian paths) are G-different if there is a subgraph isomorphic to G in their union. In this paper we prove that the maximal number of pairwise triangle-different Hamiltonian paths is equal to the number of balanced bipartitions of the ground set, answering a question of Körner, Messuti and Simonyi.