Iskanje po repozitoriju

Ključne besede: toughness, minimally tough graph, P4-free graph, complete multipartite graph, co-chordal graph, complement of forest, join of graphs
Objavljeno v RUP: 14.09.2025; Ogledov: 213; Prenosov: 17
Celotno besedilo (1,16 MB)

Opis: Let ▫$W(G)$▫ be the Wiener index of a graph ▫$G$▫. We say that a vertex ▫$v \in V(G)$▫ is a Šoltés vertex in ▫$G$▫ if ▫$W(G - v) = W(G)$▫, i.e. the Wiener index does not change if the vertex ▫$v$▫ is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ▫$G$▫ with the property that all vertices of ▫$G$▫ are Šoltés vertices. The only such graph known to this day is ▫$C_{11}$▫. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ▫$k$▫ Šoltés vertices; or one may look for ▫$\alpha$▫-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ▫$\alpha$▫. Note that the original problem is, in fact, to find all ▫$1$▫-Šoltés graphs. We intuitively believe that every ▫$1$▫-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ▫$r\ge 1$▫ we describe a construction of an infinite family of cubic ▫$2$▫-connected graphs with at least ▫$2^r$▫ Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ▫$1$▫-Šoltés graph. We are only able to provide examples of large ▫$\frac{1}{3}$▫-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ▫$1$▫-Šoltés graph other than ▫$C_{11}$▫ exists.
Ključne besede: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Objavljeno v RUP: 10.09.2025; Ogledov: 186; Prenosov: 2
Celotno besedilo (456,75 KB)

Opis: In this paper, we give a comprehensive overview of the development of clique algo-rithms and their use for drug design based on the search for cliques in protein productgraphs. The maximum clique problem is a computational problem of finding largest sub-sets of vertices in a graph that are all pairwise adjacent. A related problem is the maximumweight clique problem and the highest weight k-clique problem, which both extend the al-gorithm to weighted graphs. The review covers our developed algorithms, starting with ourimproved branch-and-bound algorithm for finding maximum cliques in undirected graphsfrom 2007 up to the recent developments of algorithms for weighted graphs in 2024. Weshow the application of these algorithms to early stages of drug discovery, in particular toprotein binding site detection based on protein similarity search in large protein databasesand to protein-ligand molecular docking.
Ključne besede: cliques, protein product graphs, applications
Objavljeno v RUP: 08.08.2025; Ogledov: 357; Prenosov: 12
Celotno besedilo (506,72 KB)
Gradivo ima več datotek! Več...

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

Ključne besede: permanent, indecomposable matrices, graphs
Objavljeno v RUP: 03.01.2022; Ogledov: 2023; Prenosov: 32
Celotno besedilo (278,69 KB)