Hamiltonian path saturated graphs with small size |
| |
Authors: | Aneta Dudek |
| |
Institution: | a Faculty of Applied Mathematics AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland b Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary |
| |
Abstract: | A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is Kn-1∪K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size. |
| |
Keywords: | 05C35 |
本文献已被 ScienceDirect 等数据库收录! |
|