Families of graph-different Hamilton paths

Details Families of graph-different Hamilton paths Families of graph-different Hamilton paths

2011-06-19

arxiv.org/abs/1106.3754v1

Mathematics

Combinatorics

Scientific paper

Let D 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 K_n 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 how to generalize our cycle-difference problems and present an example where cycles are replaced by 4-cliques. These problems are in a natural duality to those of graph intersection, initiated by Erd\"os, Simonovits and S\'os. The lack of kernel structure as a natural candidate for optimum makes our problems quite challenging.

Affiliated with

Also associated with

No associations

Rating

Families of graph-different Hamilton paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Families of graph-different Hamilton paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Families of graph-different Hamilton paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-723305