Iskanje po repozitoriju

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: 874; Prenosov: 14
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: 2400; Prenosov: 13
Celotno besedilo (526,44 KB)

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

Opis: 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.
Ključne besede: generalized Petersen graphs, I-graphs, Hamiltonian cycles, Eulerian tours, Cayley multigraphs
Objavljeno v RUP: 03.01.2022; Ogledov: 2675; Prenosov: 26
Celotno besedilo (1,01 MB)

Opis: A complete list of all connected arc-transitive asymmetric digraphs of in-valence and out-valence 2 on up to 1000 vertices is presented. As a byproduct, a complete list of all connected 4-valent graphs admitting a half-arc-transitive group of automorphisms on up to 1000 vertices is obtained. Several graph-theoretical properties of the elements of our census are calculated and discussed.
Ključne besede: graphs, digraphs, edge-transitive, vertex-transitive, arc-transitive, half arc-transitive
Objavljeno v RUP: 31.12.2021; Ogledov: 2702; Prenosov: 21
Celotno besedilo (370,47 KB)