41. Hamiltonian cycles in Cayley graphs whose order has few prime factorsKlavdija Kutnar, Dragan Marušič, D. W. Morris, Joy Morris, Primož Šparl, 2012, izvirni znanstveni članek Opis: 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$▫. Ključne besede: graph theory, Cayley graphs, hamiltonian cycles Objavljeno v RUP: 15.10.2013; Ogledov: 3609; Prenosov: 121 Celotno besedilo (545,91 KB) |
42. |
43. Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groupsŠtefko Miklavič, Primož Šparl, 2012, izvirni znanstveni članek Opis: 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. Ključne besede: graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group Objavljeno v RUP: 15.10.2013; Ogledov: 2884; Prenosov: 143 Povezava na celotno besedilo |
44. A spectral proof of the uniqueness of a strongly regular graph with parameters (81, 20, 1, 6)Dragan Stevanović, Marko Milošević, 2009, izvirni znanstveni članek Opis: We give a new proof that there exists a unique strongly regular graph with parameters (81, 20, 1, 6). Unlike the finite geometry approach used by Brouwerand haemers, we use linear algebra and spectral graph theory concepts, namely the technique of star complements, in our proof. Ključne besede: graph theory Objavljeno v RUP: 15.10.2013; Ogledov: 2814; Prenosov: 32 Povezava na celotno besedilo |
45. On bipartite Q-polynominal distance-regular graphsŠtefko Miklavič, 2007, izvirni znanstveni članek Opis: Let ▫$\Gamma$▫ denote a bipartite ▫$Q$▫-polynomial distance-regular graph with vertex set ▫$X$▫, diameter ▫$d \ge 3$▫ and valency ▫$k \ge 3$▫. Let ▫${\mathbb{R}}^X$▫ denote the vector space over ▫$\mathbb{R}$▫ consisting of column vectors with entries in ▫$\mathbb{r}$▫ and rows indexed by ▫$X$▫. For ▫$z \in X$▫, let ▫$\hat{z}$▫ denote the vector in ▫${\mathbb{R}}^X$▫ with a 1 in the ▫$z$▫-coordinate, and 0 in all other coordinates. Fix ▫$x,y \in X$▫ such that ▫$\partial(x,y)=2▫, where ▫$\partial$▫ denotes the path-length distance. For ▫$0 \le i,j \le d$▫ define ▫$w_{ij} = \sum\hat{z}$▫, where the sum is over all ▫$z \in X$▫ such that ▫$\partial(x,z) = i$▫ and ▫$\partial(y,z) = j▫$. We define ▫$W = \textrm{span} \{w_{ij}|0 \le i,j \le d\}$▫. In this paper we consider the space ▫$MW = \textrm{span} \{mw |m \in M, w \in W \l\}$▫, where ▫$M$▫ is the Bose-Mesner algebra of ▫$\Gamma$▫. We observe that ▫$MW$▫ is the minimal ▫$A$▫-invariant subspace of ▫${\mathbb{R}}^X$▫ which contains ▫$W$▫, where ▫$A$▫ is the adjacency matrix of ▫$\Gamma$▫. We display a basis for ▫$MW$▫ that is orthogonal with respect to the dot product. We give the action of ▫$A$▫ on this basis. We show that the dimension of ▫$MW$▫ is ▫$3d-3$▫ if ▫$\Gamma$▫ is 2-homogeneous, ▫$3d-1$▫ if ▫$\Gamma$▫ is the antipodal quotient of the ▫$2d$▫-cube, and ▫$4d-4$▫ otherwise. We obtain our main result using Terwilliger's "balanced set" characterization of the ▫$Q$▫-polynomial property. Ključne besede: mathematics, graph theory, distance-regular graphs, ▫$Q$▫-polynominal property, Bose-Mesner algebra, balanced set characterization of the Q-polynominal property Objavljeno v RUP: 15.10.2013; Ogledov: 3792; Prenosov: 28 Povezava na celotno besedilo |
46. |
47. On Hamiltonicity of circulant digraphs of outdegree threeŠtefko Miklavič, Primož Šparl, 2009, izvirni znanstveni članek Opis: 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\}$▫. Ključne besede: graph theory, circulant digraph, Hamilton cycle Objavljeno v RUP: 15.10.2013; Ogledov: 3068; Prenosov: 101 Povezava na celotno besedilo |
48. |
49. Hamilton paths and cycles in vertex-transitive graphs of order 6pKlavdija Kutnar, Primož Šparl, 2009, izvirni znanstveni članek Opis: 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. Ključne besede: graph theory, vertex-transitive, Hamilton cycle, Hamilton path, automorphism group Objavljeno v RUP: 15.10.2013; Ogledov: 3505; Prenosov: 40 Povezava na celotno besedilo |
50. Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power orderEdward Dobson, 2010, izvirni znanstveni članek Opis: We show that almost every Cayley graph ▫$\Gamma$▫ of an abelian group ▫$G$▫ of odd prime-power order has automorphism group as small as possible. Additionally, we show that almost every Cayley (di)graph ▫$\Gamma$▫ of an abelian group ▫$G$▫ of odd prime-power order that does not have automorphism group as small as possible is a normal Cayley (di)graph of ▫$G$▫ (that is, ▫$G_L \triangleleft {\rm Aut}(\Gamma))$▫. Ključne besede: mathematics, graph theory, Cayley graph, abelian group, automorphism group, asymptotic, ▫$p$▫-group Objavljeno v RUP: 15.10.2013; Ogledov: 4710; Prenosov: 137 Povezava na celotno besedilo |