Browsing by Subject "traceable graph"

Now showing 1 - 4 of 4

Access status: Open Access ,
Extremal traceable graphs with non-traceable edges
(2009) Wojda, Adam Paweł
By $\text{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 $\text{NT}(n)$ has been considered by Balińska and co-authors in a paper published in 2003, where it was proved that the maximum size tmax(n) of a graph in $\text{NT}(n)$ is at least $(n^2-5n+14)/2$ (for $n \geq 12$). The authors also found $t_{\max}(n)$ for $5 \leq n \leq 11$. We prove that, for $n \geq 5$, $t_{\max}(n) = max\left\{ {{n-2}\choose{2}}+4, {{n-\lfloor\frac{n-1}{2}\rfloor}\choose{2}}+\lfloor\frac{n-1}{2}\rfloor^2\right\}$ and, moreover, we characterize the extremal graphs (in fact we prove that these graphs are exactly those already described in the paper by Balinska et al.). We also prove that a traceable graph of order $n \geq 5$ may have at most $\lceil\frac{n-3}{2}\rceil \lfloor\frac{n-3}{2}\rfloor$ non traceable edges (this result was conjectured in the mentioned paper by Balinska and co-authors).
Access status: Restricted ,
Krawędzie nietrasowalne w grafach dwudzielnych prawie zrównoważonych
(Data obrony: 2018-04-24) Pawłowski, Kamil
Wydział Matematyki Stosowanej
Access status: Restricted ,
Krawędzie nietrasowalne w grafach trasowalnych
(Data obrony: 2012-12-03) Rapacz, Mateusz
Wydział Matematyki Stosowanej
Access status: Restricted ,
O grafach objazdowo jednorodnych
(Data obrony: 2012-10-29) Ślęzak, Piotr
Wydział Matematyki Stosowanej