1. The Sierpiński product of graphsJurij Kovič, Tomaž Pisanski, Sara Sabrina Zemljič, Arjana Žitnik, 2023, izvirni znanstveni članek Opis: In this paper we introduce a product-like operation that generalizes the construction of the generalized Sierpiński graphs. Let ▫$G, \, H$▫ be graphs and let ▫$f: V(G) \to V(H)$▫ be a function. Then the Sierpiński product of graphs ▫$G$▫ and ▫$H$▫ with respect to ▫$f$▫, denoted by ▫$G\otimes_f H$▫, is defined as the graph on the vertex set ▫$V(G) \times V(H)$▫, consisting of ▫$|V(G)|$▫ copies of ▫$H$▫; for every edge ▫$\{g, g'\}$▫ of ▫$G▫$ there is an edge between copies ▫$gH$▫ and ▫$g'H$▫ of form ▫$\{(g, f(g'), (g', f(g))\}$▫. Some basic properties of the Sierpiński product are presented. In particular, we show that the graph ▫$G\otimes_f H$▫ is connected if and only if both graphs ▫$G$▫ and ▫$H$▫ are connected and we present some conditions that ▫$G, \, H$▫ must fulfill for ▫$G\otimes_f H$▫ to be planar. As for symmetry properties, we show which automorphisms of ▫$G$▫ and ▫$H$▫ extend to automorphisms of ▫$G\otimes_f H$▫. In several cases we can also describe the whole automorphism group of the graph ▫$G\otimes_f H$▫. Finally, we show how to extend the Sierpiński product to multiple factors in a natural way. By applying this operation ▫$n$▫ times to the same graph we obtain an alternative approach to the well-known ▫$n$▫-th generalized Sierpiński graph. Ključne besede: Sierpiński graphs, graph products, connectivity, planarity, symmetry Objavljeno v RUP: 06.11.2023; Ogledov: 545; Prenosov: 4 Celotno besedilo (526,44 KB) |
2. Regular antilatticesKarin Cvetko-Vah, Michael Kinyon, Jonathan Leech, Tomaž Pisanski, 2019, izvirni znanstveni članek Opis: Antilattices ▫$(S; \vee, \wedge)$▫ for which the Green's equivalences ▫$\mathcal{L}_{(\vee)}$▫, ▫$\mathcal{R}_{(\vee)}$▫, ▫$\mathcal{L}_{(\wedge)}$▫ and ▫$\mathcal{R}_{(\wedge)}$▫ are all congruences of the entire antilattice are studied and enumerated. Ključne besede: noncommutative lattice, antilattice, Green's equivalences, lattice of subvarieties, enumeration, partition, composition Objavljeno v RUP: 03.01.2022; Ogledov: 1326; Prenosov: 17 Celotno besedilo (308,07 KB) |
3. Splittable and unsplittable graphs and configurationsNino Bašić, Jan Grošelj, Branko Grünbaum, Tomaž Pisanski, 2019, izvirni znanstveni članek Opis: We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic ▫$(n_3)$▫ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the Möbius-Kantor configuration are splittable. Ključne besede: configuration of points and lines, unsplittable configuration, unsplittable graph, independent set, Levi graph, Grünbaum graph, splitting type, cyclic Haar graph Objavljeno v RUP: 03.01.2022; Ogledov: 1169; Prenosov: 20 Celotno besedilo (355,79 KB) |
4. Combinatorial configurations, quasiline arrangements, and systems of curves on surfacesJürgen Bokowski, Jurij Kovič, Tomaž Pisanski, Arjana Žitnik, 2018, izvirni znanstveni članek Ključne besede: pseudoline arrangement, quasiline arrangement, projective plane, incidence structure, combinatorial configuration, topological configuration, geometric configuration, sweep, wiring diagram, allowable sequence of permutations, maps on surfaces Objavljeno v RUP: 02.01.2022; Ogledov: 1028; Prenosov: 19 Celotno besedilo (3,66 MB) |
5. Vertex-transitive graphs and their arc-typesMarston D. E. Conder, Tomaž Pisanski, Arjana Žitnik, 2017, izvirni znanstveni članek Opis: Let ▫$X$▫ be a finite vertex-transitive graph of valency ▫$d$▫, and let ▫$A$▫ be the full automorphism group of ▫$X$▫. Then the arc-type of ▫$X$▫ is defined in terms of the sizes of the orbits of the stabiliser ▫$A_v$▫ of a given vertex ▫$v$▫ on the set of arcs incident with ▫$v$▫. Such an orbit is said to be self-paired if it is contained in an orbit ▫$\Delta$▫ of ▫$A$▫ on the set of all arcs of v$X$▫ such that v$\Delta$▫ is closed under arc-reversal. The arc-type of ▫$X$▫ is then the partition of ▫$d$▫ as the sum ▫$n_1 + n_2 + \dots + n_t + (m_1 + m_1) + (m_2 + m_2) + \dots + (m_s + m_s)$▫, where ▫$n_1, n_2, \dots, n_t$▫ are the sizes of the self-paired orbits, and ▫$m_1,m_1, m_2,m_2, \dots, m_s,m_s$▫ are the sizes of the non-self-paired orbits, in descending order. In this paper, we find the arc-types of several families of graphs. Also we show that the arc-type of a Cartesian product of two "relatively prime" graphs is the natural sum of their arc-types. Then using these observations, we show that with the exception of ▫$1+1$▫ and ▫$(1+1)$▫, every partition as defined above is \emph{realisable}, in the sense that there exists at least one vertex-transitive graph with the given partition as its arc-type. Ključne besede: symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, cartesian product, covering graph Objavljeno v RUP: 02.01.2022; Ogledov: 1104; Prenosov: 20 Celotno besedilo (475,17 KB) |
6. 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: 02.01.2022; Ogledov: 1038; Prenosov: 17 Celotno besedilo (1,01 MB) |
7. Edge-contributions of some topological indices and arboreality of molecular graphsTomaž Pisanski, Janez Žerovnik, 2009, izvirni znanstveni članek Opis: Some graph invariants can be computed by summing certain values, called edge-contributions over all edges of graphs. In this note we use edge-contributions to study relationships among three graph invariants, also known as topological indices in mathematical chemistry: Wiener index, Szeged index and recently introduced revised Szeged index. We also use the quotient between the Wiener index and the revised Szeged index to study tree-likeness of graphs. Ključne besede: mathematical chemistry, chemical graph theory, topological index, revised Szeged index Objavljeno v RUP: 30.12.2021; Ogledov: 1221; Prenosov: 20 Celotno besedilo (158,93 KB) |
8. |
9. Point-ellipse configurations and related topicsGábor Gévay, Nino Bašić, Jurij Kovič, Tomaž Pisanski, 2021, izvirni znanstveni članek Ključne besede: point-line configuration, conic section, point-ellipse configuration, point-conic configuration, Levi graph, Carnot's theorem Objavljeno v RUP: 17.10.2021; Ogledov: 1701; Prenosov: 22 Povezava na celotno besedilo |
10. |