کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423992 | 1632593 | 2011 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Families of Very Different Paths Families of Very Different Paths](/preview/png/6423992.png)
Let DâN be an arbitrary subset of the natural numbers. For every n, let M(n,D) be the maximum of the cardinality of a set of Hamiltonian paths in the complete graph Kn such that the union of any two paths from the family contains a not necessarily induced cycle of some length from D. We determine or bound the asymptotics of M(n,D) in various special cases. This problem is closely related to that of the permutation capacity of graphs and constitutes a further extension of the problem area around Shannon capacity. We also discuss more ambitious generalizations where paths are replaced by other graphs. These problems are in a natural duality to those of graph intersection, initiated by ErdÅs, Simonovits and Sós. The lack of kernel structure as a natural candidate for optimum makes our problems quite challenging.
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 529-533