All Questions
3 questions
0
votes
0
answers
65
views
Cycles in Kneser graphs with three vertices forming triangles
Consider the Kneser graphs G=K(n,k). Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in G, such that any three consecutive vertices form ...
6
votes
0
answers
108
views
Localizing Bondy's metaconjecture on hamiltonicity
Definitions:
Let G be a graph on n vertices. G is Hamiltonian provided G has a cycle of length n. G is pancyclic provided G has a cycle of length ℓ for every 3≤ℓ≤n.
...
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if G=L(H) is the line graph of H, then we can reduce the problem of finding a Hamiltonian cycle in G to finding an ...