Lupa

Iskanje po repozitoriju Pomoč

A- | A+ | Natisni
Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 10 / 10
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Vertex-transitive graphs and their arc-types
Marston 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: 03.01.2022; Ogledov: 770; Prenosov: 18
.pdf Celotno besedilo (475,17 KB)

2.
Testing whether the lifted group splits
Rok 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: 707; Prenosov: 17
.pdf Celotno besedilo (317,95 KB)

3.
Sectional split extensions arising from lifts of groups
Rok Požar, 2013, izvirni znanstveni članek

Opis: Covering techniques have recently emerged as an effective tool used for classification of several infinite families of connected symmetric graphs. One commonly encountered technique is based on the concept of lifting groups of automorphisms along regular covering projections ▫$\wp \colon \tilde{X} \to X$▫. Efficient computational methods are known for regular covers with cyclic or elementary abelian group of covering transformations CT▫$(\wp)$▫. In this paper we consider the lifting problem with an additional condition on how a group should lift: given a connected graph ▫$X$▫ and a group ▫$G$▫ of its automorphisms, find all connected regular covering projections ▫$\wp \colon \tilde{X} \to X$▫ along which ▫$G$▫ lifts as a sectional split extension. By this we mean that there exists a complement ▫$\overline{G}$▫ of CT▫$(\wp)$▫ within the lifted group ▫$\tilde{G}$▫ such that ▫$\overline{G}$▫ has an orbit intersecting each fibre in at most one vertex. As an application, all connected elementary abelian regular coverings of the complete graph ▫$K_4$▫ along which a cyclic group of order 4 lifts as a sectional split extension are constructed.
Ključne besede: covering projection, graph, group extension, lifting automorphisms, voltage assignment
Objavljeno v RUP: 31.12.2021; Ogledov: 988; Prenosov: 3
.pdf Celotno besedilo (365,16 KB)

4.
5.
6.
Semisymmetric elementary abelian covers of the Möbius-Kantor graph
Aleksander Malnič, Dragan Marušič, Štefko Miklavič, Primož Potočnik, 2007, izvirni znanstveni članek

Opis: Let ▫$\wp_N : \tilde{X} \to X$▫ be a regular covering projection of connected graphs with the group of covering transformations isomorphic to ▫$N$▫. If ▫$N$▫ is an elementary abelian ▫$p$▫-group, then the projection ▫$\wp_N$▫ is called ▫$p$▫-elementary abelian. The projection ▫$\wp_N$▫ is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of Aut ▫$X$▫ lifts along ▫$\wp_N$▫, and semisymmetric if it is edge- but not vertex-transitive. The projection ▫$\wp_N$▫ is minimal semisymmetric if ▫$\wp_N$▫ cannot be written as a composition ▫$\wp_N = \wp \circ \wp_M$▫ of two (nontrivial) regular covering projections, where ▫$\pw_M$▫ is semisymmetric. Finding elementary abelian covering projections can be grasped combinatorially via a linear representation of automorphisms acting on the first homology group of the graph. The method essentially reduces to finding invariant subspaces of matrix groups over prime fields (see [A. Malnic, D. Marušic, P. Potocnik, Elementary abelian covers of graphs, J. Algebraic Combin. 20 (2004) 71-97]). In this paper, all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius-Kantor graph, the Generalized Petersen graph GP(8,3), are constructed. No such covers exist for ▫$p=2$▫. Otherwise, the number of such covering projections is equal to ▫$(p-1)/4$▫ and ▫$1+(p-1)/4$▫ in cases ▫$p \equiv 5,9,13,17,21 \pmod{24}$▫ and ▫$p \equiv 1 \pmod{24}$▫, respectively, and to ▫$(p+1)/4$▫ and ▫$1+(p+1)/4$▫ in cases ▫$p \equiv 3,7,11,15,23 \pmod{24}$▫ and ▫$p \equiv 19 \pmod{24}$▫, respectively. For each such covering projection the voltage rules generating the corresponding covers are displayed explicitly.
Ključne besede: mathematics, graph theory, graph, covering projection, lifting automorphisms, homology group, group representation, matrix group, invariant subspaces
Objavljeno v RUP: 03.04.2017; Ogledov: 2330; Prenosov: 86
URL Povezava na celotno besedilo

7.
On the split structure of lifted groups
Aleksander Malnič, Rok Požar, 2016, izvirni znanstveni članek

Opis: Let ▫$\wp \colon \tilde{X} \to X$▫ be a regular covering projection of connected graphs with the group of covering transformations ▫$\rm{CT}_\wp$▫ being abelian. Assuming that a group of automorphisms ▫$G \le \rm{Aut} X$▫ lifts along $\wp$ to a group ▫$\tilde{G} \le \rm{Aut} \tilde{X}$▫, the problem whether the corresponding exact sequence ▫$\rm{id} \to \rm{CT}_\wp \to \tilde{G} \to G \to \rm{id}$▫ splits is analyzed in detail in terms of a Cayley voltage assignment that reconstructs the projection up to equivalence. In the above combinatorial setting the extension is given only implicitly: neither ▫$\tilde{G}$▫ nor the action ▫$G\to \rm{Aut} \rm{CT}_\wp$▫ nor a 2-cocycle ▫$G \times G \to \rm{CT}_\wp$▫, are given. Explicitly constructing the cover ▫$\tilde{X}$▫ together with ▫$\rm{CT}_\wp$▫ and ▫$\tilde{G}$▫ as permutation groups on ▫$\tilde{X}$▫ is time and space consuming whenever ▫$\rm{CT}_\wp$▫ is large; thus, using the implemented algorithms (for instance, HasComplement in Magma) is far from optimal. Instead, we show that the minimal required information about the action and the 2-cocycle can be effectively decoded directly from voltages (without explicitly constructing the cover and the lifted group); one could then use the standard method by reducing the problem to solving a linear system of equations over the integers. However, along these lines we here take a slightly different approach which even does not require any knowledge of cohomology. Time and space complexity are formally analyzed whenever ▫$\rm{CT}_\wp$▫ is elementary abelian.
Ključne besede: algorithm, abelian cover, Cayley voltages, covering projection, graph, group extension, group presentation, lifting automorphisms, linear systems over the integers, semidirect product
Objavljeno v RUP: 15.10.2015; Ogledov: 2675; Prenosov: 157
.pdf Celotno besedilo (422,56 KB)

8.
Computational aspects of lifting automorphisms
Rok Požar, 2015, objavljeni povzetek znanstvenega prispevka na konferenci

Ključne besede: covering projection, graph, lifting automorphsim
Objavljeno v RUP: 15.10.2015; Ogledov: 2129; Prenosov: 13
URL Povezava na celotno besedilo

9.
On 2-fold covers of graphs
Yan-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: 3533; Prenosov: 34
URL Povezava na celotno besedilo

10.
Rose window graphs underlying rotary maps
István Kovács, Klavdija Kutnar, János Ruff, 2010, objavljeni znanstveni prispevek na konferenci

Opis: Given natural numbers ▫$n \ge 3$▫ and ▫$1 \le a$▫, ▫$r \le n-1$▫, the rose window graph ▫$R_n(a,r)$▫ is a quartic graph with vertex set ▫$\{x_i \vert\; i \in {\mathbb Z}_n \} \cup \{y_i \vert\; i \in {\mathbb Z}_n \}$▫ and edge set ▫$\{\{x_i, x_{i+1}\} \vert\; i \in {\mathbb Z}_n \} \cup \{\{y_i, y_{i+1}\} \vert\; i \in {\mathbb Z}_n \} \cup \{\{x_i, y_i\} \vert\; i \in {\mathbb Z}_n\} \cup \{\{x_{i+a}, y_i\} \vert\; i \in {\mathbb Z}_n \}$▫. In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map.
Ključne besede: graph theory, rotary map, edge-transitive graph, covering graph, voltage graph
Objavljeno v RUP: 15.10.2013; Ogledov: 3475; Prenosov: 87
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.05 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici