1. Binary coding of resonance graphs of catacondensed polyhexesAleksander Vesel, 2023, izvirni znanstveni članek Opis: A catacondensed polyhex H is a connected subgraph of a hexagonal system such that any edge of H lies in a hexagon of H, any triple of hexagons of H has an empty intersection and the inner dual of H is a cactus graph. A perfect matching M of a catacondensed polyhex H is relevant if every cycle of the inner dual of H admitsa vertex that corresponds to the hexagon which contributes three edges in M. The vertex set of the graph R˜(H) consists of all relevant perfect matchings of H, two perfect matchings being adjacent whenever their symmetric difference forms the edge set of a hexagon of H. A labeling that assigns in linear time a binary string to every relevant perfect matching of a catacondensed polyhex is presented. The introduced labeling defines an isometric embedding of R˜(H)
into a hypercube. Ključne besede: graphs, graph theory, resonance graphs Objavljeno v DKUM: 07.06.2024; Ogledov: 34; Prenosov: 1 Celotno besedilo (518,69 KB) Gradivo ima več datotek! Več... |
2. Generalized cut method for computing Szeged-like polynomials with applications to polyphenyls and carbon nanoconesSimon Brezovnik, Niko Tratnik, 2023, izvirni znanstveni članek Opis: Szeged, Padmakar-Ivan (PI), and Mostar indices are some of the most investigated distance-based Szeged-like topological indices. On the other hand, the polynomials related to these topological indices were also introduced, for example the Szeged polynomial, the edge- Szeged polynomial, the PI polynomial, the Mostar polynomial, etc. In this paper, we introduce a concept of the general Szeged-like polynomial for a connected strength-weighted graph. It turns out that this concept includes all the above mentioned polynomials and also infinitely many other graph polynomials. As the main result of the paper, we prove a cut method which enables us to efficiently calculate a Szeged-like polynomial by using the corresponding polynomials of strength-weighted quotient graphs obtained by a partition of the edge set that is coarser than ▫$\Theta^*$▫-partition. To the best of our knowledge, this represents the first implementation of the famous cut method to graph polynomials. Finally, we show how the deduced cut method can be applied to calculate some Szeged-like polynomials and corresponding topological indices of para-polyphenyl chains and carbon nanocones. Ključne besede: graph theory, carbon nanocone, topological indices Objavljeno v DKUM: 25.03.2024; Ogledov: 157; Prenosov: 3 Povezava na celotno besedilo |
3. Hereditarnia 2019 : Book of Abstracts, Maribor, 21st & 22nd June, 20192019, druge monografije in druga zaključena dela Opis: The booklet contains the abstracts of the talks given at the 22th Hereditarnia Workshop on Graph Properties that was held at the Faculty of Electrical Engineering and Computer Science in Maribor on 21st and 22nd of June, 2019. The workshop attracted 22 participants from 8 countries. All of the participants are researchers in di˙erent areas of graph theory, but at this event they all presented topics connected with (hereditary) graph properties. Themes of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings, graph domination, some graph dimensions matchings and graph products. Beside the abstracts of the plenary speaker (Roman Sotak) and three invited speakers (Tanja Gologranc, Michael A. Henning and Ismael G. Yero), the booklet also contains the abstracts of 7 contributed talks given at the event. Ključne besede: mathematics, graph theory, Hereditarnia, Maribor, Slovenia Objavljeno v DKUM: 13.12.2019; Ogledov: 1260; Prenosov: 330 Celotno besedilo (1,08 MB) Gradivo ima več datotek! Več... |
4. Ljubljana-Leoben graph theory seminar : Maribor, 13.-15. September, 2017. Book of abstracts2017, druge monografije in druga zaključena dela Opis: The booklet contains the abstracts of the talks given at the 30th Ljubljana-Leoben Graph Theory Seminar that was held at the Faculty of Natural Sciences and Mathematics in Maribor between 13-15 September, 2017. The seminar attracted more than 30 participants from eight countries, all of which are researchers in different areas of graph theory. The topics of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings (b-coloring, packing coloring, edge colorings), graph domination (rainbow domination, Grundy domination, graph security), distinguishing problems, algebraic graph theory, graph algorithms, chemical graph theory, coverings, matchings and also some classical extremal problems. Beside the abstracts of the four invited speakers (Csilla Bujtás, Premysl Holub, Jakub Przybyło, Zsolt Tuza), the booklet contains also the abstracts of 18 contributed talks given at the event. Ključne besede: mathematics, discrete mathematics, graph theory, Ljubljana-Leoben seminar, Maribor, Slovenia Objavljeno v DKUM: 08.12.2017; Ogledov: 1530; Prenosov: 195 Celotno besedilo (457,62 KB) Gradivo ima več datotek! Več... |
5. Omega polynomial revisitedMircea V. Diudea, Sandi Klavžar, 2010, izvirni znanstveni članek Opis: Omega polynomial was proposed by Diudea (Omega Polynomial, Carpath. J. Math., 2006, 22, 43-47) to count the opposite topologically parallel edges in graphs, particularly to describe the polyhedral nanostructures. In this paper, the main definitions are re-analyzed and clear relations with other three related polynomials are established. These relations are supported by close formulas and appropriate examples. Ključne besede: mathematics, chemical graph theory, counting polynomials, Ommega polynomial, Theta polynomial, Pi polynomial, PI index, Sadhana polynomial, Cluj-Ilmenau index, CI index Objavljeno v DKUM: 24.08.2017; Ogledov: 995; Prenosov: 113 Celotno besedilo (263,85 KB) Gradivo ima več datotek! Več... |
6. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2012, izvirni znanstveni članek Opis: Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from $\{0,1,2\}$. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give ▫$O(C)$▫ time algorithm for computing Roman domination number of special classes of polygraphs (rota- and fasciagraphs). By implementing the algorithm we give formulas for Roman domination number of the Cartesian products of paths and cycles ▫$P_n \Box P_k$▫, ▫$P_n \Box C_k$▫ for ▫$k \leq 8$▫ and ▫$n \in {\mathbb N}$▫ and for ▫$C_n \Box P_k$▫ and ▫$C_n \Box C_k$▫ for ▫$k \leq 5$▫, ▫$n \in {\mathbb N}$▫. We also give a list of Roman graphs among investigated families. Ključne besede: graph theory, Roman domination number, Cartesian product, polygraphs, path algebra Objavljeno v DKUM: 23.08.2017; Ogledov: 1560; Prenosov: 237 Celotno besedilo (719,06 KB) Gradivo ima več datotek! Več... |
7. Altered Wiener indicesDamir Vukičević, Janez Žerovnik, 2005, izvirni znanstveni članek Opis: Recently Nikolić, Trinajstić and Randić put forward a novel modification ▫$^mW(G)$▫ of the Wiener number ▫$W(G)$▫, called modified Wiener index, which definition was generalized later by Gutman and the present authors. Here we study another class of modified indices defined as ▫$W_{min,λ}(G) = ∑(V(G)^λm_G(u,ν)^λ−m_G(u,ν)^{2λ})$▫ and show that some of the important properties of ▫$W(G)$▫, ▫$^mW(G)$▫ and ▫$^λW(G)$▫ are also properties of ▫$W_{min,λ}(G)$▫, valid for most values of the parameter λ. In particular, if ▫$T_n$▫ is any n-vertex tree, different from the n-vertex path ▫$P_n$▫ and the n-vertex star ▫$S_n$▫, then for any λ ≥ 1 or λ < 0, ▫$^W_{min,λ}(P_n) > W_{min,λ}(T_n)>W_{min,λ}(S_n)$▫. Thus for these values of the parameter λ, ▫$W_{min,λ}(G)$▫ provides a novel class of structure-descriptors, suitable for modeling branching-dependent properties of organic compounds, applicable in QSPR and QSAR studies. We also demonstrate that if trees are ordered with regard to ▫$W_{min,λ}(G)$▫ then, in the general case, this ordering is different for different λ. Ključne besede: mathematics, chemical graph theory, Wiener index, modified Wiener index Objavljeno v DKUM: 17.08.2017; Ogledov: 1163; Prenosov: 118 Celotno besedilo (991,46 KB) Gradivo ima več datotek! Več... |
8. The number of moves of the largest disc in shortest paths on Hanoi graphsSimon Aumann, Katharina Götz, Andreas Hinz, Ciril Petr, 2014, izvirni znanstveni članek Opis: In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs ▫$H_p^n$▫ in a more general setting. Here ▫$p$▫ stands for the number of pegs and ▫$n$▫ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of largest disc moves (LDMs). The patterns of these LDMs will be coded as binary strings of length ▫$p-1$▫ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all ▫$n \geqslant p(p-2)$▫, of optimal paths where ▫$p-1$▫ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC. Ključne besede: graph theory, Tower of Hanoi, Hanoi graphs, shortest paths, symmetries, breadth-first search Objavljeno v DKUM: 14.08.2017; Ogledov: 1655; Prenosov: 234 Celotno besedilo (376,70 KB) Gradivo ima več datotek! Več... |
9. Linear recognition of generalized Fibonacci cubes $Q_h (111)$Yoomi Rho, Aleksander Vesel, 2016, izvirni znanstveni članek Opis: The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 ... b_h$ containing no three consecutive 1’s. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time. Ključne besede: graph theory, Fibonacci cubes, recognition algorithm Objavljeno v DKUM: 10.07.2017; Ogledov: 1300; Prenosov: 206 Celotno besedilo (803,81 KB) Gradivo ima več datotek! Več... |
10. Efficient open domination in graph productsDorota Kuziak, Iztok Peterin, Ismael G. Yero, 2014, izvirni znanstveni članek Opis: A graph ▫$G$▫ is an efficient open domination graph if there exists a subset ▫$D$▫ of ▫$V(G)$▫ for which the open neighborhoods centered in vertices of ▫$D$▫ form a partition of ▫$V(G)$▫. We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the Cartesian product we give a characterization when one factor is ▫$K_2$▫. Ključne besede: graph theory, efficient open domination, graph products, total domination Objavljeno v DKUM: 10.07.2017; Ogledov: 1288; Prenosov: 150 Celotno besedilo (804,78 KB) Gradivo ima več datotek! Več... |