|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 3 of 9 found articles
| Title: |
Extremal traceable graphs with non-traceable edges |
| Author: |
Adam Paweł Wojda |
| Appeared in: |
Opuscula mathematica |
| Paging: | Volume 29 (2009) nr. 1 pages 89-92 |
| Year: |
2009 |
| Contents: |
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(n)$ 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 $(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\{ {{n-2}\choose{2}}+4, {{n-\lfloor\frac{n-1}{2}\rfloor}\choose{2}}+\lfloor\frac{n-1}{2}\rfloor\}^2$ 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). |
| Publisher: |
AGH University of Science and Technology (provided by DOAJ) |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 3 of 9 found articles
| << previous | next >> |