Artykuł
Extremal traceable graphs with non-traceable edges
| creativeworkseries.issn | 1232-9274 | |
| dc.contributor.author | Wojda, Adam Paweł. | |
| dc.date.issued | 2009 | |
| dc.description.abstract | 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). | en |
| dc.description.version | wersja wydawnicza | |
| dc.identifier.eissn | 2300-6919 | |
| dc.identifier.issn | 1232-9274 | |
| dc.identifier.nukat | dd2009318064 | |
| dc.identifier.uri | https://repo.agh.edu.pl/handle/AGH/50104 | |
| dc.language.iso | eng | |
| dc.rights | Attribution 4.0 International | |
| dc.rights.access | otwarty dostęp | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/legalcode | |
| dc.subject | traceable graph | en |
| dc.subject | non-traceable edge | en |
| dc.title | Extremal traceable graphs with non-traceable edges | en |
| dc.title.related | Opuscula Mathematica | |
| dc.type | artykuł | |
| dspace.entity.type | Publication | |
| publicationissue.issueNumber | No. 1 | |
| publicationissue.pagination | pp. 89-92 | |
| publicationvolume.volumeNumber | Vol. 29 | |
| relation.isJournalIssueOfPublication | f1fe7ce8-8d89-46cc-b797-447d94992b06 | |
| relation.isJournalIssueOfPublication.latestForDiscovery | f1fe7ce8-8d89-46cc-b797-447d94992b06 | |
| relation.isJournalOfPublication | 304b3b9b-59b9-4830-9178-93a77e6afbc7 |
Pliki
Pakiet podstawowy
1 - 1 z 1
Ładuję...
- Nazwa:
- 29-1-08.pdf
- Rozmiar:
- 266.94 KB
- Format:
- Adobe Portable Document Format
- Opis:
- Artykuł z czasopisma