1. On edge connectivity of direct products of graphsXiang-Lan Cao, Špela Brglez, Simon Špacapan, Elkin Vumar, 2011, original scientific article Abstract: Let ▫$lambda(G)$▫ be the edge connectivity of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫ is the graph with vertex set ▫$V(G times H) = V(G) times V(H)$▫, where two vertices ▫$(u_1,v_1)$▫ and ▫$(u_2,v_2)$▫ are adjacent in ▫$G times H$▫ if ▫$u_1u_2 in E(G)$▫ and ▫$v_1v_2 in E(H)$▫. We prove that ▫$lambda(G times K_n) = min{n(n-1)lambda(G), (n-1)delta(G)}$▫ for every nontrivial graph ▫$G$▫ and ▫$n geqslant 3$▫. We also prove that for almost every pair of graphs ▫$G$▫ and ▫$H$▫ with ▫$n$▫ vertices and edge probability ▫$p$▫, ▫$G times H$▫ is ▫$k$▫-connected, where ▫$k=O((n/log n)^2)$▫. Keywords: mathematics, graph theory, combinatorial problems, connectivity, direct product, graph product, separating set Published: 01.06.2012; Views: 1568; Downloads: 183 Link to full text |
2. Acceleration of sweep-line technique by employing smart quicksortDavid Podgorelec, Gregor Klajnšek, 2005, original scientific article Abstract: Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm 'vertex sort'. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertexsort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (inlinear time) than random cases. We have named the combined algorithm 'smartquicksort' because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm. Keywords: computational geometry, quicksort, smart quicksort, sweep-line, smart quicksort, polygon triangualation, vertex sort Published: 01.06.2012; Views: 1296; Downloads: 59 Link to full text |
3. Identification of critical points for the design and synthesis of flexible processesZorka Novak-Pintarič, Zdravko Kravanja, 2008, original scientific article Abstract: Optimization problems for the design and synthesis of flexible chemical processes are often associated with highly discretized models. The ultimate goal of this work is to significantly reduce the set of uncertain parameter points used in these problems. To accomplish the task, an approach was developed for identifying the minimum set of critical points needed for flexible design. Critical points in this work represent those values of uncertain parameters that determine optimal overdesign of process, so that feasible operation is assured within the specified domain of uncertain parameters. The proposed approach identifies critical values of uncertain parameters a-priori by the separate maximization of each design variable, together with simultaneous optimization of the economic objective function. During this procedure, uncertain parameters are transformed into continuous variables. Three alternative methods are proposed within this approach: the formulation based on Karush-Kuhn-Tucker (KKT) optimality conditions, the iterative two-level method, and the approximate one-level method. The identified critical points are then used for the discretization of infinite uncertain problems, in order to obtain the design with the optimum objective function and flexibility index at unity. All three methods can identify vertex or even nonvertex critical points, whose total number is less than or equal to the number of design variables, which represents a significant reduction in the problem's dimensionality. Some examples are presented illustrating the applicability and efficiency of the proposed approach, as well as the role of the critical points in the optimization of design problems under uncertainty. Keywords: chemical processing, process synthesis, flexibility, design, critical point, vertex, nonvertex Published: 01.06.2012; Views: 1123; Downloads: 62 Link to full text |
4. Distance-balanced graphsJanja Jerebic, Sandi Klavžar, Douglas F. Rall, 2005 Abstract: V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov. Keywords: matematika, teorija grafov, razdalja, razdaljno uravnoteženi grafi, produkti grafov, povezanost, mathematics, graph theory, graph distance, distance-balanced graphs, graph products, connectivity Published: 10.07.2015; Views: 597; Downloads: 59 Link to full text |
5. Edge, vertex and mixed fault-diametersIztok Banič, Rija Erveš, Janez Žerovnik, 2008 Abstract: Let ▫${mathcal{D}}^E_q(G)$▫ denote the diameter of a graph ▫$G$▫ after deleting any of its ▫$q$▫ edges, and ▫${mathcal{D}}^V_p(G)$▫ denote the diameter of ▫$G$▫ after deleting any of its ▫$p$▫ vertices. We prove that ▫${mathcal{D}}^E_a(G) le {mathcal{D}}^V_a(G) + 1$▫ a for all meaningful ▫$a$▫. We also define mixed fault diameter ▫${mathcal{D}}^M_{(p,q)}(G)$▫, where ▫$p$▫ vertices and ▫$q$▫ edges are deleted at the same time. We prove that for ▫$0 < l le a$▫, ▫${mathcal{D}}^E_a(G) le {mathcal{D}}^M_{(a-l,l)}(G) le {mathcal{D}}^V_a(G) + 1$▫, and give some examples. Keywords: matematika, teorija grafov, povezanost, mathematics, (vertex)-connectivity, edge-connectivity, (vertex) fault-diameter, edge-fault diameter, interconnection network Published: 10.07.2015; Views: 438; Downloads: 57 Link to full text |
6. Graphʼs theory approach for searching the shortest routing path in RIP protocolSaša Klampfer, Jože Mohorko, Žarko Čučej, Amor Chowdhury, 2012, original scientific article Abstract: Routing is a problem domain with an infinite number of final-solutions. One of the possible approaches to solving such problems is using graph theory. This paper presents mathematical analysis methodologies based on circular graphs for solving a shortest path routing problem. The problem is focused on searching for the shortest path within a circular graph. Such a search coincides with the network routing problem domain. In this paper, we introduce in the detail all necessary parts needed to understand such an approach. This includes: definition of the routing problem domain, introduction to circular graphs and their usage, circular graphʼs properties, definition of walks through a circular graph, searching and determining the shortest path within a circular graph, etc. The state of the art routing methods, implemented in contemporary highly sophisticated routers, includes well-known weight-based algorithms and distance-vectors-based algorithms. The proposed solution can be placed between the two abovementioned methods. Each of these known methods strives for optimal results, but each of them also has its own deficiencies, which should be rectified with the proposed new method. This theoretically presented method is argued by a practical example and compared with the RIP (Routing Information Protocol) technique, where we look for the shortest path and possible walks through a specified circular graph. Keywords: circular graphs, shortest path, graph diameter, walk through, CIGRP, connectivity matrix, network topology, symmetry, fully connected graph Published: 10.07.2015; Views: 1037; Downloads: 49 Link to full text |
7. On the k-path vertex cover of some graph productsMarko Jakovac, Andrej Taranenko, 2013, original scientific article Abstract: A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ▫$psi_k$▫(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$psi_k$▫, moreover ▫$psi_2$▫ and ▫$psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given. Keywords: matematika, teorija grafov, vozliščno pokritje, po poteh vozliščno pokritje, disociacijsko število, neodvisnostno število, grafovski produkti, mathematics, graph theory, vertex cover, path vertex cover, dissociation number, independence number, graph products Published: 10.07.2015; Views: 506; Downloads: 10 Link to full text |
8. A counterexample to the uniform shortest path routing conjecture for vertex-transitive graphsJozef Širáň, Sangho Shim, Janez Žerovnik, 2000, published scientific conference contribution abstract Keywords: matematika, teorija grafov, po vozliščih prehodni grafi, najkrajše poti, krepki produkt, mathematics, graph theory, vertex-transitive graphs, shortest paths, strong product Published: 10.07.2015; Views: 368; Downloads: 11 Link to full text |
9. Gutman, Ivan; Miljković, Olga: Molecules with smallest connectivity indices. - Match No. 41 (2000), 57-70Sandi Klavžar, 2001, review, book review, critique Keywords: matematika, kemijska teorija grafov, molekularni grafi, indeksi povezanosti, mathematics, chemical graph theory, molecular graphs, connectivity indices Published: 10.07.2015; Views: 563; Downloads: 20 Link to full text |
10. Edge, vertex and mixed fault diametersIztok Banič, Rija Erveš, Janez Žerovnik, 2009, original scientific article Abstract: Let ▫${mathcal{D}}^E_q(G)$▫ denote the maximum diameter among all subgraphs obtained by deleting ▫$q$▫ edges of ▫$G$▫. Let ▫${mathcal{D}}^V_p(G)$▫ denote the maximum diameter among all subgraphs obtained by deleting ▫$p$▫ vertices of ▫$G$▫. We prove that ▫${mathcal{D}}^E_a(G) leqslant {mathcal{D}}^V_a(G) + 1$▫ a for all meaningful ▫$a$▫. We also define mixed fault diameter ▫${mathcal{D}}^M_{(p,q)}(G)$▫, where ▫$p$▫ vertices and ▫$q$▫ edges are deleted at the same time. We prove that for ▫$0 < l leqslant a$▫, ▫${mathcal{D}}^E_a(G) leqslant {mathcal{D}}^M_{(a-ell,ell)}(G) leqslant {mathcal{D}}^V_a(G) + 1$▫, and give some examples. Keywords: vertex-connectivity, edge-connectivity, vertex fault diameter, edge fault diameter, mixed fault diameter, interconnection network Published: 10.07.2015; Views: 465; Downloads: 58 Link to full text |