Portal de Periódicos da CAPES

Some Hamiltonian results in powers of graphs

1973; The National Institute of Standards and Technology; Volume: 77B; Issue: 1 and 2 Linguagem: Inglês

10.6028/jres.077b.001

2376-5291

Arthur M. Hobbs,

Limits and Structures in Graph Theory

In this paper we show that the connectivity of the kth power of a graph of connectivity m is at least km if the kth power of the graph is not a complete graph.Also, we.prove th at removing as many as k -2 vertices from the kth power of a graph (k ;;. 3) leaves a Hamiltonian graph, and that removing as many as k -3 vertices from the kth power of a graph (k;;' 3) leaves a Hamiltonian con nected graph.Further, if every vertex of a graph has degree two or more, then the square of th e graph contai ns a 2-factor.Finally, we show that the squares of certain Euler graphs are Hamiltonian.