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


1 - 7 / 7
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
Vertex cover at distance on H-free graphs
Clément Jean Dallard, Mirza Krbezlija, Martin Milanič, 2021, objavljeni znanstveni prispevek na konferenci

Ključne besede: distance-k vertex cover, H-free graph, np-completeness, polynomial-time algorithm, dichotomy
Objavljeno v RUP: 16.07.2021; Ogledov: 560; Prenosov: 27
URL Povezava na polno besedilo

Graphs vertex-partitionable into strong cliques
Ademir Hujdurović, 2019, izvirni znanstveni članek

Ključne besede: canonical double cover, Cayley graph, generalized Cayley graph
Objavljeno v RUP: 28.06.2019; Ogledov: 1190; Prenosov: 226
URL Povezava na polno besedilo

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: 2217; Prenosov: 150
.pdf Polno besedilo (422,56 KB)

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