Ciclos e Caminhos Longos em Grafos Ímpares

• Felipe de Campos Mesquita UFABC
• Letícia Rodrigues Bueno UFABC

Abstract

The odd graph O_k is the graph whose vertices are all subsets with k elements of a set that has n elements, and two vertices are joined by an edge if the corresponding pair of k-subsets is disjoint. A conjecture due to Biggs claims that O_k is hamiltonian for k≥3 and a conjecture due to Lovász implies that O_k has a hamiltonian path for k≥1. From a hamiltonian cycle in O_k-1, we show how to construct a cycle in Ok with at least 75% of the vertices of O_k. Additionally, we prove that, for each k, the odd graph has a path with at least 50% of the vertices of O_k.

References

Biggs, N. (1979). Some odd graph theory. Ann. New York Acad. Sci., 319:71–81.

Bueno, L. R., Faria, L., Figueiredo, C. M. H., and Fonseca, G. D. (2009). Hamiltonian paths in odd graphs. Appl. Anal. Discrete Math., 3(2):386–394.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.

Gilbert, E. N. (1958). Gray codes and paths on the n-cube. Bell Systems Tech. J., 37:815– 826.

Gray, F. (1953). Pulse code communication. U.S. Patent 2632058.

Havel, I. (1983). Semipaths in directed cubes. In Fiedler, M., editor, Graphs and other Combinatorial Topics, pages 101–108, Teubner, Leipzig. Teubner-Texte Math.

Johnson, J. R. (2004). Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A, 105(2):255–271.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. and Thatcher, J., editors, Complexity of Computer Computations, pages 85–103, New York. Plenum Press.

Lovász, L. (1970). Problem 11. In Combinatorial Structures and their Applications. Gordon and Breach.

Savage, C. D. and Winkler, P. (1995). Monotone gray codes and the middle levels problem. J. Combin. Theory Ser. A, 70(2):230–248.

Shields, I. and Savage, C. D. (2004). A note on hamilton cycles in Kneser graphs. Bulletin of the Institute for Combinatorics and Its Applications, 40:13–22.