Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
vidyarthi's user avatar
  • 2,089
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 3n. ...
D. Ror.'s user avatar
  • 399
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 ...
Felix Goldberg's user avatar