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 University Press
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/}
}
[1] 1. Bondy, J. A., Pancyclic graphs, Proc. Second Louisiana Conference on Combinatorics, Graph Theory and Computing, 167–172, Louisiana State University Baton Rouge, La., 1971. Google Scholar
[2] 2. Edmonds, J., Existence of k-edge connected ordinary graphs with prescribed degrees, J. Res. Nat. Bur. Standards Sect. B 68B (1964), 73–74. Google Scholar
[3] 3. Harary, F., Graph Theory. (Addison-Wesley, Reading, Mass. 1969). Google Scholar
Cité par Sources :