81. Vertex-transitive graphs and their arc-typesMarston 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: 2993; Downloads: 26
 Full text (475,17 KB) |
82. Mathematical aspects of fullerenesVesna Andova, František Kardoš, Riste Škrekovski, 2016, original scientific article Abstract: Fullerene graphs are cubic, 3-connected, planar graphs with exactly 12 pentagonal faces, while all other faces are hexagons. Fullerene graphs are mathematical models of fullerene molecules, i.e., molecules comprised only by carbon atoms different than graphites and diamonds. We give a survey on fullerene graphs from our perspective, which could be also considered as an introduction to this topic. Different types of fullerene graphs are considered, their symmetries, and construction methods. We give an overview of some graph invariants that can possibly correlate with the fullerene molecule stability, such as: the bipartite edge frustration, the independence number, the saturation number, the number of perfect matchings, etc.
Keywords: fullerene, cubic graph, planar graph, topological indices
Published in RUP: 03.01.2022; Views: 2461; Downloads: 21
Full text (626,25 KB) |
83. Mathematical aspects of Wiener indexMartin Knor, Riste Škrekovski, Aleksandra Tepeh, 2016, original scientific article Abstract: The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this article we summarize some results, conjectures and problems on this molecular descriptor, with emphasis on works we were involved in.
Keywords: Wiener index, total distance, topological index, molecular descriptor, chemical graph theory
Published in RUP: 03.01.2022; Views: 3856; Downloads: 49
Full text (434,58 KB) |
84. On colour-preserving automorphisms of Cayley graphsAdemir 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: 2239; Downloads: 35
Full text (412,93 KB) |
85. Testing whether the lifted group splitsRok Požar, 2016, original scientific article Abstract: 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.
Keywords: algorithm, graph, group extension, lifting automorphisms, regular covering projection, voltages
Published in RUP: 03.01.2022; Views: 2267; Downloads: 37
Full text (317,95 KB) |
86. On minimal forbidden subgraphs for the class of EDM-graphsGašper Jaklič, Jolanda Modic, 2015, original scientific article Abstract: In this paper, a relation between graph distance matrices and Euclidean distance matrices (EDM) is considered. Graphs, for which the distance matrix is not an EDM (NEDM-graphs), are studied. All simple connected non-isomorphic graphs on ▫$n \le 8$▫ nodes are analysed and a characterization of the smallest NEDM-graphs, i.e., the minimal forbidden subgraphs, is given. It is proven that bipartite graphs and some subdivisions of the smallest NEDM-graphs are NEDM-graphs, too.
Keywords: graph theory, graph, Euclidean distance matrix, distance, eigenvalue
Published in RUP: 31.12.2021; Views: 2341; Downloads: 21
Full text (711,65 KB) |
87. The automorphism groups of non-edge transitive rose window graphsEdward Tauscher Dobson, István Kovács, Štefko Miklavič, 2015, original scientific article Abstract: In this paper, we determine the full automorphism groups of rose window graphs that are not edge-transitive. As the full automorphism groups of edge-transitive rose window graphs have been determined, this complete the problem of calculating the full automorphism group of rose window graphs. As a corollary, we determine which rose window graphs are vertex-transitive. Finally, we determine the isomorphism classes of non-edge-transitive rose window graphs.
Keywords: rose window graphs, automorphism group, isomorphism problem, vertex-transitive graph
Published in RUP: 31.12.2021; Views: 2566; Downloads: 43
Full text (275,74 KB) |
88. Some recent discoveries about half-arc-transitive graphs : dedicated to Dragan Marušič on the occasion of his 60th birthdayMarston D. E. Conder, Primož Potočnik, Primož Šparl, 2015, original scientific article Abstract: We present some new discoveries about graphs that are half-arc-transitive (that is, vertex- and edge-transitive but not arc-transitive). These include the recent discovery of the smallest half-arc-transitive 4-valent graph with vertex-stabiliser of order 4, and the smallest with vertex-stabiliser of order 8, two new half-arc-transitive 4-valent graphs with dihedral vertex-stabiliser ▫$D_4$▫ (of order 8), and the first known half-arc-transitive 4-valent graph with vertex-stabiliser of order 16 that is neither abelian nor dihedral. We also use half-arc-transitive group actions to provide an answer to a recent question of Delorme about 2-arc-transitive digraphs that are not isomorphic to their reverse.
Keywords: graph, edge-transitive, vertex-transitive, arc-transitive, half arc-transitive
Published in RUP: 31.12.2021; Views: 2572; Downloads: 23
Full text (333,06 KB) |
89. Commuting graphs and extremal centralizersGregor Dolinar, Aleksandr Èmilevič Guterman, Bojan Kuzma, Polona Oblak, 2014, original scientific article Abstract: We determine the conditions for matrix centralizers which can guarantee the connectedness of the commuting graph for the full matrix algebra ▫$M_n(\mathbb{F})$▫ over an arbitrary field ▫$\mathbb{F}$▫. It is known that if ▫$\mathbb{F}$▫ is an algebraically closed field and ▫$n \ge 3$▫, then the diameter of the commuting graph of ▫$M_n(\mathbb{F})$▫ is always equal to four. We construct a concrete example showing that if ▫$\mathbb{F}$▫ is not algebraically closed, then the commuting graph of ▫$M_n(\mathbb{F})$▫ can be connected with the diameter at least five.
Keywords: commuting graph, matrix ring, centralizer
Published in RUP: 31.12.2021; Views: 2150; Downloads: 35
Full text (228,78 KB) |
90. Sectional split extensions arising from lifts of groupsRok Požar, 2013, original scientific article Abstract: 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.
Keywords: covering projection, graph, group extension, lifting automorphisms, voltage assignment
Published in RUP: 31.12.2021; Views: 2514; Downloads: 5
Full text (365,16 KB) |
