Triangle-different Hamiltonian paths

DOI10.1016/J.JCTB.2017.09.003MaRDI QIDQ684117zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 9 February 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.05237, http://real.mtak.hu/89848/1/1608.05237v2.pdf

zbMATH Keywords

permutationsextremal combinatoricsgraph different Hamiltonian pathsShannon capacity of graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Abstract: 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"orner, Messuti and Simonyi.

Recommendations

• Path separation by short cycles
• On the hamiltonian path graph of a graph
• On mutually independent Hamiltonian paths
• Families of locally separated Hamilton paths
• Mutually orthogonal Hamiltonian connected graphs

Cites work

• Connector families of graphs
• Degree-doubling graph families
• Families of graph-different Hamilton paths
• Graph-Different Permutations
• Intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• On types of growth for graph-different permutations
• Pairwise colliding permutations and the capacity of infinite graphs
• Path separation by short cycles
• Permutation capacities of families of oriented infinite paths
• Triangle-intersecting families of graphs

Cited in

(5)

• Improved upper bounds on even-cycle creating Hamilton paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Structured Codes of Graphs
• Families of graph-different Hamilton paths
• On \(k\)-neighbor separated permutations

This page was built for publication: Triangle-different Hamiltonian paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684117)