Iskanje po repozitoriju

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: 578; Prenosov: 4
Celotno besedilo (526,44 KB)

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: 1166; Prenosov: 20
Celotno besedilo (475,17 KB)