91. A decomposition for Markov processes at an independent exponential timeMihael Perman, 2017, izvirni znanstveni članek Opis: The path of Markov process ▫$X$▫ run up to an independent exponential random time ▫$S_\theta$▫ can be decomposed into the part prior to the last exit time from a point before ▫$S_\theta$▫, and the remainder up to ▫$S_\theta$▫. In this paper the laws of the two segments are identified under suitable assumptions using excursion theory.
Objavljeno v RUP: 03.01.2022; Ogledov: 440; Prenosov: 13
 Celotno besedilo (312,49 KB) |
92. A novel characterization of cubic Hamiltonian graphs via the associated quartic graphsSimona Bonvicini, Tomaž Pisanski, 2017, izvirni znanstveni članek 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: 576; Prenosov: 16
Celotno besedilo (1,01 MB) |
93. On [plus/minus] 1 eigenvectors of graphsDragan Stevanović, 2016, izvirni znanstveni članek Opis: While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of ▫$\pm 1$▫ entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ▫$\pm 1$▫ eigenvector is quite rich, being closed under a number of different graph compositions.
Ključne besede: eigenvector, adjacency matrix, Wilf's problem
Objavljeno v RUP: 03.01.2022; Ogledov: 501; Prenosov: 25
Celotno besedilo (325,02 KB) |
94. Mathematical aspects of fullerenesVesna Andova, František Kardoš, Riste Škrekovski, 2016, izvirni znanstveni članek 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: 529; Prenosov: 16
Celotno besedilo (626,25 KB) |
95. Mathematical aspects of Wiener indexMartin Knor, Riste Škrekovski, Aleksandra Tepeh, 2016, izvirni znanstveni članek Opis: The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this article we summarize some results, conjectures and problems on this molecular descriptor, with emphasis on works we were involved in.
Ključne besede: Wiener index, total distance, topological index, molecular descriptor, chemical graph theory
Objavljeno v RUP: 03.01.2022; Ogledov: 644; Prenosov: 25
Celotno besedilo (434,58 KB) |
96. On colour-preserving automorphisms of Cayley graphsAdemir Hujdurović, Klavdija Kutnar, Dave Witte Morris, Joy Morris, 2016, izvirni znanstveni članek 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: 498; Prenosov: 16
Celotno besedilo (412,93 KB) |
97. Testing whether the lifted group splitsRok Požar, 2016, izvirni znanstveni članek Opis: Let a group of automorphisms lift along a regular covering projection of connected graphs given combinatorially by means of voltages. The data that determine the lifted group and its action are then conveniently encoded in terms of voltages as well. Along these lines, an algorithm for testing whether the lifted group is a split extension of the group of covering transformations has recently been proposed in the case when the group of covering transformations is solvable. It consists of decomposing the covering into a series of coverings with elementary abelian groups of covering transformations, and inductively solving the problem at every elementary abelian step. Although the explicit construction of the lifted group is not needed, it still involves time and space consuming constructions of certain subgroups in the lifted group at every step except at the final one. In this paper, an improved version that completely avoids such constructions is presented. From voltage distribution we first compute the weak action and the factor set that determine the lifted group, and we then carry out the test by extracting the necessary information only from the corresponding weak actions and factor sets at every step. An experimental comparison is made against the previous version.
Ključne besede: algorithm, graph, group extension, lifting automorphisms, regular covering projection, voltages
Objavljeno v RUP: 03.01.2022; Ogledov: 516; Prenosov: 17
Celotno besedilo (317,95 KB) |
98. On minimal forbidden subgraphs for the class of EDM-graphsGašper Jaklič, Jolanda Modic, 2015, izvirni znanstveni članek Opis: In this paper, a relation between graph distance matrices and Euclidean distance matrices (EDM) is considered. Graphs, for which the distance matrix is not an EDM (NEDM-graphs), are studied. All simple connected non-isomorphic graphs on ▫$n \le 8$▫ nodes are analysed and a characterization of the smallest NEDM-graphs, i.e., the minimal forbidden subgraphs, is given. It is proven that bipartite graphs and some subdivisions of the smallest NEDM-graphs are NEDM-graphs, too.
Ključne besede: graph theory, graph, Euclidean distance matrix, distance, eigenvalue
Objavljeno v RUP: 31.12.2021; Ogledov: 670; Prenosov: 15
Celotno besedilo (711,65 KB) |
99. The automorphism groups of non-edge transitive rose window graphsEdward Dobson, István Kovács, Štefko Miklavič, 2015, izvirni znanstveni članek Opis: In this paper, we determine the full automorphism groups of rose window graphs that are not edge-transitive. As the full automorphism groups of edge-transitive rose window graphs have been determined, this complete the problem of calculating the full automorphism group of rose window graphs. As a corollary, we determine which rose window graphs are vertex-transitive. Finally, we determine the isomorphism classes of non-edge-transitive rose window graphs.
Ključne besede: rose window graphs, automorphism group, isomorphism problem, vertex-transitive graph
Objavljeno v RUP: 31.12.2021; Ogledov: 644; Prenosov: 18
Celotno besedilo (275,74 KB) |
100. Some recent discoveries about half-arc-transitive graphs : dedicated to Dragan Marušič on the occasion of his 60th birthdayMarston D. E. Conder, Primož Potočnik, Primož Šparl, 2015, izvirni znanstveni članek Opis: We present some new discoveries about graphs that are half-arc-transitive (that is, vertex- and edge-transitive but not arc-transitive). These include the recent discovery of the smallest half-arc-transitive 4-valent graph with vertex-stabiliser of order 4, and the smallest with vertex-stabiliser of order 8, two new half-arc-transitive 4-valent graphs with dihedral vertex-stabiliser ▫$D_4$▫ (of order 8), and the first known half-arc-transitive 4-valent graph with vertex-stabiliser of order 16 that is neither abelian nor dihedral. We also use half-arc-transitive group actions to provide an answer to a recent question of Delorme about 2-arc-transitive digraphs that are not isomorphic to their reverse.
Ključne besede: graph, edge-transitive, vertex-transitive, arc-transitive, half arc-transitive
Objavljeno v RUP: 31.12.2021; Ogledov: 562; Prenosov: 16
Celotno besedilo (333,06 KB) |
