1. On regular graphs with Šoltés verticesNino Bašić, Martin Knor, Riste Škrekovski, 2025, izvirni znanstveni članek Opis: Let ▫$W(G)$▫ be the Wiener index of a graph ▫$G$▫. We say that a vertex ▫$v \in V(G)$▫ is a Šoltés vertex in ▫$G$▫ if ▫$W(G - v) = W(G)$▫, i.e. the Wiener index does not change if the vertex ▫$v$▫ is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ▫$G$▫ with the property that all vertices of ▫$G$▫ are Šoltés vertices. The only such graph known to this day is ▫$C_{11}$▫. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ▫$k$▫ Šoltés vertices; or one may look for ▫$\alpha$▫-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ▫$\alpha$▫. Note that the original problem is, in fact, to find all ▫$1$▫-Šoltés graphs. We intuitively believe that every ▫$1$▫-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ▫$r\ge 1$▫ we describe a construction of an infinite family of cubic ▫$2$▫-connected graphs with at least ▫$2^r$▫ Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ▫$1$▫-Šoltés graph. We are only able to provide examples of large ▫$\frac{1}{3}$▫-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ▫$1$▫-Šoltés graph other than ▫$C_{11}$▫ exists.
Ključne besede: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Objavljeno v RUP: 10.09.2025; Ogledov: 376; Prenosov: 2
 Celotno besedilo (456,75 KB) |
2. On cubic vertex-transitive graphs of given girthEdward Tauscher Dobson, Ademir Hujdurović, Wilfried Imrich, Ronald Ortner, 2025, izvirni znanstveni članek Opis: A set of vertices of a graph is distinguishing if the only automorphism that preserves it is the identity. The minimal size of such sets, if they exist, is the distinguishing cost. The distinguishing costs of vertex transitive cubic graphs are well known if they are 1-arc-transitive, or if they have two edge orbits and either have girth 3 or vertex-stabilizers of order 1 or 2. There are many results about vertex-transitive cubic graphs of girth 4 with two edge orbits, but for larger girth almost nothing is known about the distinguishing costs of such graphs. We prove that cubic vertex-transitive graphs of girth 5 with two edge orbits have distinguishing cost 2, and prove the non-existence of infinite 3-arc-transitive cubic graphs of girth 6.
Ključne besede: distinguishing number, distinguishing cost, vertex-transitive cubic graphs, automorphisms
Objavljeno v RUP: 27.08.2025; Ogledov: 676; Prenosov: 4
Celotno besedilo (451,52 KB)
Gradivo ima več datotek! Več... |
3. |
4. On 2-fold covers of graphsYan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, 2008, izvirni znanstveni članek Opis: A regular covering projection ▫$\wp : \widetilde{X} \to X$▫ of connected graphs is ▫$G$▫-admissible if ▫$G$▫ lifts along ▫$\wp$▫. Denote by ▫$\tilde{G}$▫ the lifted group, and let CT▫$(\wp)$▫ be the group of covering transformations. The projection is called ▫$G$▫-split whenever the extension ▫{$\mathrm{CT}}(\wp) \to \tilde{G} \to G$▫ splits. In this paper, split 2-covers are considered, with a particular emphasis given to cubic symmetric graphs. Supposing that ▫$G$▫ is transitive on ▫$X$▫, a ▫$G$▫-split cover is said to be ▫$G$▫-split-transitive if all complements ▫$\tilde{G} \cong G$▫ of CT▫$(\wp)$▫ within ▫$\tilde{G}$▫ are transitive on ▫$\widetilde{X}$▫; it is said to be ▫$G$▫-split-sectional whenever for each complement ▫$\tilde{G}$▫ there exists a ▫$\tilde{G}$▫-invariant section of ▫$\wp$▫; and it is called ▫$G$▫-split-mixed otherwise. It is shown, when ▫$G$▫ is an arc-transitive group, split-sectional and split-mixed 2-covers lead to canonical double covers. Split-transitive covers, however, are considerably more difficult to analyze. For cubic symmetric graphs split 2-cover are necessarily canonical double covers (that is, no ▫$G$▫-split-transitive 2-covers exist) when ▫$G$▫ is 1-regular or 4-regular. In all other cases, that is, if ▫$G$▫ is ▫$s$▫-regular, ▫$s=2,3$▫ or ▫$5$▫, a necessary and sufficient condition for the existence of a transitive complement ▫$\tilde{G}$▫ is given, and moreover, an infinite family of split-transitive 2-covers based on the alternating groups of the form ▫$A_{12k+10}$▫ is constructed. Finally, chains of consecutive 2-covers, along which an arc-transitive group ▫$G$▫ has successive lifts, are also considered. It is proved that in such a chain, at most two projections can be split. Further, it is shown that, in the context of cubic symmetric graphs, if exactly two of them are split, then one is split-transitive and the other one is either split-sectional or split-mixed.
Ključne besede: graph theory, graphs, cubic graphs, symmetric graphs, ▫$s$▫-regular group, regular covering projection
Objavljeno v RUP: 15.10.2013; Ogledov: 5993; Prenosov: 41
 Povezava na celotno besedilo |
5. A complete classification of cubic symmetric graphs of girth 6Klavdija Kutnar, Dragan Marušič, 2009, izvirni znanstveni članek Opis: A complete classification of cubic symmetric graphs of girth 6 is given. It is shown that with the exception of the Heawood graph, the Moebius-Kantor graph, the Pappus graph, and the Desargues graph, a cubic symmetric graph ▫$X$▫ of girth 6 is a normal Cayley graph of a generalized dihedral group; in particular, (i) ▫$X$▫ is 2-regular if and only if it is isomorphic to a so-called ▫$I_k^n$▫-path, a graph of order either ▫$n^2/2$▫ or ▫$n^2/6$▫, which is characterized by the fact that its quotient relative to a certain semiregular automorphism is a path. (ii) ▫$X$▫ is 1-regular if and only if there exists an integer ▫$r$▫ with prime decomposition ▫$r=3^s p_1^{e_1} \dots p_t^{e_t} > 3$▫, where ▫$s \in \{0,1\}$▫, ▫$t \ge 1$▫, and ▫$p_i \equiv 1 \pmod{3}$▫, such that ▫$X$▫ is isomorphic either to a Cayley graph of a dihedral group ▫$D_{2r}$▫ of order ▫$2r$▫ or ▫$X$▫ is isomorphic to a certain ▫$\ZZ_r$▫-cover of one of the following graphs: the cube ▫$Q_3$▫, the Pappus graph or an ▫$I_k^n(t)$▫-path of order ▫$n^2/2$▫.
Ključne besede: graph theory, cubic graphs, symmetric graphs, ▫$s$▫-regular graphs, girth, consistent cycle
Objavljeno v RUP: 15.10.2013; Ogledov: 6199; Prenosov: 96
Povezava na celotno besedilo |
