Sequences Realizable by Graphs with Hamiltonian Squares
Canadian mathematical bulletin, Tome 17 (1975) no. 5, pp. 629-631
Voir la notice de l'article provenant de la source Cambridge
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.)
Chungphaisan, V. Sequences Realizable by Graphs with Hamiltonian Squares. Canadian mathematical bulletin, Tome 17 (1975) no. 5, pp. 629-631. doi: 10.4153/CMB-1974-116-6
@article{10_4153_CMB_1974_116_6,
author = {Chungphaisan, V.},
title = {Sequences {Realizable} by {Graphs} with {Hamiltonian} {Squares}},
journal = {Canadian mathematical bulletin},
pages = {629--631},
year = {1975},
volume = {17},
number = {5},
doi = {10.4153/CMB-1974-116-6},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1974-116-6/}
}
Cité par Sources :