Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T10:37:52.552Z Has data issue: false hasContentIssue false

Sequences Realizable by Graphs with Hamiltonian Squares

Published online by Cambridge University Press:  20 November 2018

V. Chungphaisan*
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let d=(d 1,…,dn ) be a sequence of positive integers. In this note we show that d is realizable by a graph whose square is hamiltonian if and only if (i) d is realizable by some graph, (ii) n≥3, and (iii) d 1+…+d n≥2(n-1). In fact, we prove that if d is realizable by a connected graph, then d is realizable by a graph with a spanning caterpillar. From this it follows that if d is realizable by a connected graph, it is realizable by a graph whose square is pancyclic. We also prove that d is realizable by a graph with a spanning wreath if and only if d is realizable by some graph and d 1+…+dn ≥2n. (A wreath is a connected graph that has exactly one cycle and all vertices not in the cycle monovalent.)

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1975