Iskanje po repozitoriju

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: 1521; Prenosov: 19
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: 1374; Prenosov: 16
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: 1590; Prenosov: 17
Celotno besedilo (1,01 MB)

Opis: Fullerene graphs are cubic, 3-connected, planar graphs with exactly 12 pentagonal faces, while all other faces are hexagons. Fullerene graphs are mathematical models of fullerene molecules, i.e., molecules comprised only by carbon atoms different than graphites and diamonds. We give a survey on fullerene graphs from our perspective, which could be also considered as an introduction to this topic. Different types of fullerene graphs are considered, their symmetries, and construction methods. We give an overview of some graph invariants that can possibly correlate with the fullerene molecule stability, such as: the bipartite edge frustration, the independence number, the saturation number, the number of perfect matchings, etc.
Ključne besede: fullerene, cubic graph, planar graph, topological indices
Objavljeno v RUP: 03.01.2022; Ogledov: 1565; Prenosov: 18
Celotno besedilo (626,25 KB)

Opis: We study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups ▫$G$▫, such that every such automorphism of every connected Cayley graph on ▫$G$▫ has a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.
Ključne besede: Cayley graph, automorphism, colour-preserving, colour-permuting
Objavljeno v RUP: 03.01.2022; Ogledov: 1494; Prenosov: 28
Celotno besedilo (412,93 KB)