Iskanje po repozitoriju

Ključne besede: graphs, automorphism group, symmetry, locally arc-transitive graphs, symmetric graphs, cycle structure, linking ring structure
Objavljeno v RUP: 03.01.2022; Ogledov: 906; Prenosov: 18
Celotno besedilo (397,55 KB)

Opis: It has been conjectured that automorphism groups of vertex-transitive (di)graphs, and more generally 2-closures of transitive permutation groups, must necessarily possess a fixed-point-free element of prime order, and thus a non-identity element with all orbits of the same length, in other words, a semiregular element. The known affirmative answers for graphs with primitive and quasiprimitive groups of automorphisms suggest that solvable groups need to be considered if one is to hope for a complete solution of this conjecture. It is the purpose of this paper to present an overview of known results and suggest possible further lines of research towards a complete solution of the problem.
Ključne besede: solvable group, semiregular automorphism, fixed-point-free automorphism, polycirculant conjecture
Objavljeno v RUP: 03.01.2022; Ogledov: 893; Prenosov: 17
Celotno besedilo (235,26 KB)

Opis: Let ▫$\mathcal P$▫ be a polyhedron whose boundary consists of flat polygonal faces on some compact surface ▫$S(\mathcal P)$▫ (not necessarily homeomorphic to the sphere ▫$S^{2}$)▫. Let ▫$vo_{R}(\mathcal P), eo_{R}(\mathcal P)$▫, ▫$ fo_{R}(\mathcal P)$▫ be the numbers of rotational orbits of vertices, edges and faces, respectively, determined by the group ▫$G = G_{R}(P)$▫ of all the rotations of the Euclidean space ▫$E^{3}$▫ preserving ▫$\mathcal P$▫. We define the ''rotational orbit Euler characteristic'' of ▫$\mathcal P$▫ as the number ▫$Eo_{R}(\mathcal P) = vo_{R}(\mathcal P) - eo_{R}(\mathcal P) + fo_{R}(\mathcal P)$▫. Using the Burnside lemma we obtain the lower and the upper bound for ▫$Eo_{R}(\mathcal P)$▫ in terms of the genus of the surface ▫$S(P)$▫. We prove that ▫$Eo_{R} \in \lbrace 2,1,0,-1\rbrace $▫ for any convex polyhedron ▫$\mathcal P$▫. In the non-convex case ▫$Eo_{R}$▫ may be arbitrarily large or small.
Ključne besede: polyhedron, rotational orbit, Euler characteristic
Objavljeno v RUP: 03.01.2022; Ogledov: 818; Prenosov: 18
Celotno besedilo (272,96 KB)

Opis: We introduce a new edge centrality measure - relative edge betweenness ▫$\gamma (uv) = b(uv)/\sqrt{c(u)c(v)}$▫, where ▫$b(uv$)▫ is the standard edge betweenness and ▫$c(u)$▫ is the adjusted vertex betweenness. In this alternative definition, the importance of an edge is normalized with respect to the importance of its end-vertices. This gives a better presentation of the ''local'' importance of an edge, i.e. its importance in the near neighborhood. We present sharp upper and lower bounds on this invariant together with the characterization of graphs attaining these bounds. In addition, we discuss the bounds for various interesting graph families, and state several open problems.
Objavljeno v RUP: 03.01.2022; Ogledov: 736; Prenosov: 15
Celotno besedilo (261,26 KB)

Opis: We give a necessary and sufficient condition for a cubic graph to be Hamiltonian by analyzing Eulerian tours in certain spanning subgraphs of the quartic graph associated with the cubic graph by 1-factor contraction. This correspondence is most useful in the case when it induces a blue and red 2-factorization of the associated quartic graph. We use this condition to characterize the Hamiltonian ▫$I$▫-graphs, a further generalization of generalized Petersen graphs. The characterization of Hamiltonian ▫$I$▫-graphs follows from the fact that one can choose a 1-factor in any ▫$I$▫-graph in such a way that the corresponding associated quartic graph is a graph bundle having a cycle graph as base graph and a fiber and the fundamental factorization of graph bundles playing the role of blue and red factorization. The techniques that we develop allow us to represent Cayley multigraphs of degree 4, that are associated to abelian groups, as graph bundles. Moreover, we can find a family of connected cubic (multi)graphs that contains the family of connected ▫$I$▫-graphs as a subfamily.
Ključne besede: generalized Petersen graphs, I-graphs, Hamiltonian cycles, Eulerian tours, Cayley multigraphs
Objavljeno v RUP: 03.01.2022; Ogledov: 815; Prenosov: 16
Celotno besedilo (1,01 MB)