21. |
22. A note on a geometric construction of large Cayley graps of given degree and diameterGyörgy Kiss, István Kovács, Klavdija Kutnar, János Ruff, Primož Šparl, 2009, original scientific article Abstract: An infinite series and some sporadic examples of large Cayley graphs with given degree and diameter are constructed. The graphs arise from arcs, caps and other objects of finite projective spaces. Keywords: degree, diameter problem, Moore bound, finite projective spaces Published in RUP: 15.10.2013; Views: 3389; Downloads: 69 Link to full text |
23. |
24. |
25. Hamiltonian cycles in Cayley graphs whose order has few prime factorsKlavdija Kutnar, Dragan Marušič, D. W. Morris, Joy Morris, Primož Šparl, 2012, original scientific article Abstract: We prove that if Cay▫$(G; S)$▫ is a connected Cayley graph with ▫$n$▫ vertices, and the prime factorization of ▫$n$▫ is very small, then Cay▫$(G; S)$▫ has a hamiltonian cycle. More precisely, if ▫$p$▫, ▫$q$▫, and ▫$r$▫ are distinct primes, then ▫$n$▫ can be of the form kp with ▫$24 \ne k < 32$▫, or of the form ▫$kpq$▫ with ▫$k \le 5$▫, or of the form ▫$pqr$▫, or of the form ▫$kp^2$▫ with ▫$k \le 4$▫, or of the form ▫$kp^3$▫ with ▫$k \le 2$▫. Keywords: graph theory, Cayley graphs, hamiltonian cycles Published in RUP: 15.10.2013; Views: 3548; Downloads: 121 Full text (545,91 KB) |
26. |
27. Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groupsŠtefko Miklavič, Primož Šparl, 2012, original scientific article Abstract: In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph ▫$\Gamma$▫ is ▫$n$▫-HC-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton cycle of ▫$\Gamma$▫. Similarly, ▫$\Gamma$▫ is weakly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton path of ▫$\Gamma$▫. Moreover, ▫$\Gamma$▫ is strongly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if for every such path $P$ there is a Hamilton path of ▫$\Gamma$▫ starting with ▫$P$▫. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2-HC-extendable and a complete classification of 3-HC-extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4-HP-extendable. Keywords: graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group Published in RUP: 15.10.2013; Views: 2846; Downloads: 143 Link to full text |
28. |
29. On Hamiltonicity of circulant digraphs of outdegree threeŠtefko Miklavič, Primož Šparl, 2009, original scientific article Abstract: This paper deals with Hamiltonicity of connected loopless circulant digraphs of outdegree three with connection set of the form ▫$\{a,ka,c\}$▫, where ▫$k$▫ is an integer. In particular, we prove that if ▫$k=-1$▫ or ▫$k=2$▫ such a circulant digraph is Hamiltonian if and only if it is not isomorphic to the circulant digraph on 12 vertices with connection set ▫$\{3,6,4\}$▫. Keywords: graph theory, circulant digraph, Hamilton cycle Published in RUP: 15.10.2013; Views: 3014; Downloads: 101 Link to full text |
30. Hamilton paths and cycles in vertex-transitive graphs of order 6pKlavdija Kutnar, Primož Šparl, 2009, original scientific article Abstract: It is shown that every connected vertex-transitive graph of order ▫$6p$▫, where ▫$p$▫ is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order ▫$6p$▫ which is not genuinely imprimitive contains a Hamilton cycle. Keywords: graph theory, vertex-transitive, Hamilton cycle, Hamilton path, automorphism group Published in RUP: 15.10.2013; Views: 3461; Downloads: 40 Link to full text |