Extremal traceable graphs with non-traceable edges

• Autorzy: Wojda A. P.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

traceable graph; non-traceable edge

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 1
• Strony: 89--92
• Opis fizyczny: Bibliogr. 2 poz.

Twórcy

autor

Wojda A. P.

• AGH University of Science and Technology, Faculty of Applied Mathematics, Chair of Discrete Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland,

Bibliografia

• [1] K.T. Balińska, K.T. Zwierzyński, M.I. Gargano, L.V. Quintas, Extremal size problems for graphs with non-traceable edges, Congressus Numerantium 162 (2003), 55-64.
• [2] Z. Skupień, A.P. Wojda, Extremal non-(p,q)- hamiltonian graphs, Studia Scienciarum Mathematicarum Hungarica 10 (1975), 323-328.