21. 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: 2097; Prenosov: 19
 Celotno besedilo (1,01 MB) |
22. The automorphism groups of non-edge transitive rose window graphsEdward Tauscher 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: 2361; Prenosov: 38
Celotno besedilo (275,74 KB) |
23. A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two : dedicated to Dragan Marušič on the occasion of his 60th birthdayPrimož Potočnik, Pablo Spiga, Gabriel Verret, 2015, izvirni znanstveni članek Opis: A complete list of all connected arc-transitive asymmetric digraphs of in-valence and out-valence 2 on up to 1000 vertices is presented. As a byproduct, a complete list of all connected 4-valent graphs admitting a half-arc-transitive group of automorphisms on up to 1000 vertices is obtained. Several graph-theoretical properties of the elements of our census are calculated and discussed.
Ključne besede: graphs, digraphs, edge-transitive, vertex-transitive, arc-transitive, half arc-transitive
Objavljeno v RUP: 31.12.2021; Ogledov: 2150; Prenosov: 19
Celotno besedilo (370,47 KB) |
24. |
25. The recognition problem of graph search trees read moreJesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2021, izvirni znanstveni članek Ključne besede: search tree recognition, LBFS, LDFS, MNS, MCS, chordal graphs
Objavljeno v RUP: 18.10.2021; Ogledov: 3361; Prenosov: 30
 Povezava na celotno besedilo |
26. |
27. Parallelizing an algorithm to find the maximal clique on interval graphs on graphical processing unitsChristian Trefftz, Andrés Santamaría-Galvis, Roberto Cruz Rodes, 2014, objavljeni znanstveni prispevek na konferenci Ključne besede: graph theory, graphics processing units, parallel algorithms, CUDA, Thrust library, interval graphs, maximal clique
Objavljeno v RUP: 18.10.2021; Ogledov: 2445; Prenosov: 25
Povezava na celotno besedilo |
28. Ramamurthy, Balaji; Bapat, Ravindra Bhalchandra; Goel, Shivani: Distance matrices perturbed by Laplacians. (English summary). - Appl. Math. 65 (2020), no. 5, 599-607.Marko Orel, 2021, recenzija, prikaz knjige, kritika Ključne besede: Laplacian of a graph, positive definite matrices, weighted graphs
Objavljeno v RUP: 18.10.2021; Ogledov: 1958; Prenosov: 9
Povezava na celotno besedilo |
29. |
30. |
