- Tytuł:
- Extremal traceable graphs with non-traceable edges
- Autorzy:
- Wojda, A. P.
- Powiązania:
- https://bibliotekanauki.pl/articles/255301.pdf
- Data publikacji:
- 2009
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
traceable graph
non-traceable edge - Opis:
- By NT(n) we denote the set of graphs of order n which are traceable but have non-traceable edges, i.e. edges which are not contained in any hamiltonian path. The class NT(re) has been considered by Balińska and co-authors in a paper published in 2003, where it was proved that the maximum size t(max)(n) of a graph in NT(n) is at least (n2-5n+14)/2 (for n≥ 12). The authors also found t(max)(n) for 5 ≤ n ≤ 11. We prove that, for n n≥ 5, t(max) (n) = max {(n-2/2) + 4, [formula] and, moreover, we characterize the extremal graphs (in fact we prove that these graphs are exactly those already described in the paper by Balińska et al). We also prove that a traceable graph of order n n≥ 5 may have at most [n-3/2] [n-3/2] non traceable edges (this result was conjectured in the mentioned paper by Balińska and co-authors).
- Źródło:
-
Opuscula Mathematica; 2009, 29, 1; 89-92
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł