Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: traceable graph

Sortuj według:

Ogranicz wyniki do:

Extremal traceable graphs with non-traceable edges

Wojda A. P.

Opuscula Mathematica

2009

Vol. 29, no. 1

89-92

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).