Lupa

Search the repository Help

A- | A+ | Print
Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 62
First pagePrevious page1234567Next pageLast page
1.
2.
Vertex-transitive graphs and their arc-types
Marston D. E. Conder, Tomaž Pisanski, Arjana Žitnik, 2017, original scientific article

Abstract: 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.
Keywords: symmetry type, vertex-transitive graph, arc-transitive graph, Cayley graph, cartesian product, covering graph
Published in RUP: 03.01.2022; Views: 768; Downloads: 18
.pdf Full text (475,17 KB)

3.
A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs
Simona Bonvicini, Tomaž Pisanski, 2017, original scientific article

Abstract: 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.
Keywords: generalized Petersen graphs, I-graphs, Hamiltonian cycles, Eulerian tours, Cayley multigraphs
Published in RUP: 03.01.2022; Views: 746; Downloads: 16
.pdf Full text (1,01 MB)

4.
On colour-preserving automorphisms of Cayley graphs
Ademir Hujdurović, Klavdija Kutnar, Dave Witte Morris, Joy Morris, 2016, original scientific article

Abstract: We study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups ▫$G$▫, such that every such automorphism of every connected Cayley graph on ▫$G$▫ has a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.
Keywords: Cayley graph, automorphism, colour-preserving, colour-permuting
Published in RUP: 03.01.2022; Views: 682; Downloads: 16
.pdf Full text (412,93 KB)

5.
Reachability relations, transitive digraphs and groups
Aleksander Malnič, Primož Potočnik, Norbert Seifter, Primož Šparl, 2015, original scientific article

Abstract: In [A. Malnič, D. Marušič, N. Seifter, P. Šparl and B. Zgrablič, Reachability relations in digraphs, Europ. J. Combin. 29 (2008), 1566-1581] it was shown that properties of digraphs such as growth, property ▫$\mathbf{Z}$▫, and number of ends are reflected by the properties of certain reachability relations defined on the vertices of the corresponding digraphs. In this paper we study these relations in connection with certain properties of automorphism groups of transitive digraphs. In particular, one of the main results shows that if atransitive digraph admits a nilpotent subgroup of automorphisms with finitely many orbits, then its nilpotency class and the number of orbits are closely related to particular properties of reachability relations defined on the digraphs in question. The obtained results have interesting implications for Cayley digraphs of certain types of groups such as torsion-free groups of polynomial growth.
Keywords: Cayley digraph, reachability relation
Published in RUP: 31.12.2021; Views: 784; Downloads: 16
.pdf Full text (311,92 KB)

6.
Regular Cayley maps for dihedral groups
István Kovács, Young Soo Kwon, 2021, original scientific article

Keywords: regular map, Cayley map, dihedral group
Published in RUP: 18.01.2021; Views: 952; Downloads: 33
URL Link to full text

7.
8.
A finite simple group is CCA if and only if it has no element of order four
Luke Morgan, Joy Morris, Gabriel Verret, 2020, original scientific article

Keywords: CCA problem, Cayley graphs, edge-colouring
Published in RUP: 02.12.2020; Views: 1018; Downloads: 34
URL Link to full text

9.
10.
Search done in 0 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica