Change search
ReferencesLink to record
Permanent link

Direct link
Some cyclic properties of graphs with local Ore-type conditions
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle.

In this thesis we investigate two classes of graphs, defined by local criteria. Graphs in these classes, with a simple set of exceptions K, were proven to be Hamiltonian by Asratian, Broersma, van den Heuvel, and Veldman in 1996 and by Asratian in 2006, respectively.

We prove here that in addition to being Hamiltonian, graphs in these classes have stronger cyclic properties. In particular, we prove that if a graph G belongs to one of these classes, then for each vertex x in G there is a sequence of cycles such that each cycle contains the vertex x, and

  • the shortest cycle in the sequence has length at most 5;
  • the longest cycle in the sequence is a Hamilton cycle (unless G belongs to the set of exceptions K, in which case the longest cycle in the sequence contains all but one vertex of G);
  • each cycle in the sequence except the first contains all vertices of the previous cycle, and at most two other vertices.

Furthermore, for each edge e in G that does not lie on a triangle, there is a sequence of cycles with the same three properties, such that each cycle in the sequence contains the edge e.

Place, publisher, year, edition, pages
2016. , 57 p.
Series
, LiTH-MAT-EX, 2016/04
Keyword [en]
Hamiltonian, pancyclic, vertex pancyclic, edge pancyclic, cycle extendable, local conditions, Ore-type conditions
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-129213ISRN: LiTH-MAT-EX--2016/04--SEOAI: oai:DiVA.org:liu-129213DiVA: diva2:1048002
Subject / course
Mathematics
Supervisors
Examiners
Available from: 2016-11-21 Created: 2016-06-13 Last updated: 2016-11-21Bibliographically approved

Open Access in DiVA

fulltext(618 kB)12 downloads
File information
File name FULLTEXT01.pdfFile size 618 kBChecksum SHA-512
7ae9d18437b9665c5d6b980f5b5d5e26b68a733a863ce3315733480393f5f9d8f477d74bc772adf77319c65ac0d5798b620a25819dda62a04d22a7710288793d
Type fulltextMimetype application/pdf

Other links

http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-129213

Search in DiVA

By author/editor
Granholm, Jonas
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 12 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 81 hits
ReferencesLink to record
Permanent link

Direct link