Hamiltonian path saturated graphs with small size

Dudek, A; Katona, GY [Katona, Gyula Y. (gráfelmélet), szerző] Számítástudományi és Információelméleti Tanszék (BME / VIK); Wojda, AP

Angol nyelvű Tudományos Szakcikk (Folyóiratcikk)
Megjelent: DISCRETE APPLIED MATHEMATICS 0166-218X 1872-6771 154 (9) pp. 1372-1379 2006
  • SJR Scopus - Applied Mathematics: Q2
Szakterületek:
    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 it has size at most ((n-1)(2)) and, for n >= 6, the only HPS graph of order n and size ((n-1)(2)) is Kn-1 boolean OR K-1. 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 G(n) 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 P-m-saturated graphs with small size. (c) 2006 Elsevier B.V. All rights reserved.
    Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
    2022-01-20 11:30