1. Relations between polynomials based on perfect matchings and independent sets of CERSNiko Tratnik, Petra Žigert Pleteršek, 2026, original scientific article Abstract: In this paper, we firstly focus on catacondensed even ring systems (shortly CERS) without any linearly connected adjacent triple of f inite faces. For such a graph G, we describe a bijection between the set of all perfect matchings (Kekulé structures) of G and the set of all independent sets of the inner dual of G, which enables us to prove the equality between three polynomials: the sextet polynomial of G, the independence polynomial of the inner dual of G, and the newly introduced link polynomial of G. These equalities imply that the number of perfect matchings of G equals the number of resonant sets of G and also the number of independent sets of the inner dual of G. Moreover, we show that the number of edges of the resonance graph of G coincides with the derivative of the mentioned polynomials evaluated at x = 1. Finally, we provide the generalization of the results to all peripherally 2-colorable graphs.
Keywords: graph theory, resonance graphs, polynomials
Published in DKUM: 01.10.2025; Views: 0; Downloads: 5
 Full text (473,85 KB)
This document has many files! More... |
2. |
3. On the Wiener-like root-indices of graphsSimon Brezovnik, Matthias Dehmer, Niko Tratnik, Petra Žigert Pleteršek, 2025, original scientific article Abstract: In this paper, we examine roots of graph polynomials where those roots can be considered as structural graph measures. More precisely, we prove analytical results for the roots of certain modified graph polynomials and also discuss numerical results. As polynomials, we use, e.g., the Hosoya, the Schultz, and the Gutman polynomial which belong to an interesting family of degree-distance-based graph polynomials; they constitute so-called counting polynomials with non-negative integers as coefficients and the roots of their modified versions have been used to characterize the topology of graphs. Our results can be applied for the quantitative characterization of graphs. Besides analytical results on bounds and convergence, we also investigate other properties of those measures such as their degeneracy which is an undesired aspect of graph measures. It turns out that the measures representing roots of graph polynomials possess high discrimination power on exhaustively generated trees, which outperforms standard versions of these indices. Furthermore, a new measure is introduced that allows us to compare different topological indices in terms of structure sensitivity and abruptness.
Keywords: graph theory, Hosoya polynomial, Schultz polynomial, Gutman polynomial, root-index, discrimination power, structure sensitivity
Published in DKUM: 03.07.2025; Views: 0; Downloads: 5
Full text (1,29 MB)
This document has many files! More... |
4. |
5. |
6. |
7. |
8. The Graovac-Pisanski index of connected bipartite graphs with applications to hydrocarbon moleculesMatevž Črepnjak, Martin Knor, Niko Tratnik, Petra Žigert Pleteršek, 2021, original scientific article Abstract: The Graovac-Pisanski index, also called the modified Wiener index, was introduced in 1991 and represents an extension of the original Wiener index, because it considers beside the distances in a graph also its symmetries. Similarly as Wiener in 1947 showed the correlation of the Wiener indices of the alkane series with the boiling points, in 2018 the connection between the GraovacPisanski index and the melting points of some hydrocarbon molecules was established. In this paper, we prove that the Graovac-Pisanski index of any connected bipartite graph as well as of any connected graph on an even number of vertices is an integer number. These results are applied to some important families of hydrocarbon molecules. By using a computer programme, the graphs with a non-integer Graovac-Pisanski index on at most nine vertices are counted. Finally, an infinite class of unicyclic graphs with a non-integer Graovac-Pisanski index is described.
Keywords: modified Wiener index, Graovac-Pisanski index, graph distance, automorphism group, hydrocarbons, carbon nanostructures
Published in DKUM: 14.02.2025; Views: 0; Downloads: 8
Full text (1,36 MB)
This document has many files! More... |
9. Resonance graphs of plane bipartite graphs as daisy cubesSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2025, original scientific article Keywords: daisy cube, fries number, peripherally 2-colorable, plane (weakly) elementary bipartite graph, resonance graph
Published in DKUM: 31.01.2025; Views: 0; Downloads: 1
Full text (646,39 KB)
This document has many files! More... |
10. Zagreb root-indices of graphs with chemical applicationsNiko Tratnik, Petra Žigert Pleteršek, 2024, original scientific article Abstract: Root-indices of graphs are mathematical tools that help us to understand complex systems, like molecules and networks, by capturing key structural information. In this study, we introduce two new root-indices, the first and the second Zagreb root-index, and we analyze their properties. We apply these indices to chemical structures like benzenoid molecules and octane isomers, showing that they sometimes provide better insights than traditional indices. We also compare the effectiveness of several root-indices with their standard versions, highlighting their ability to distinguish between different graph structures.
Keywords: first Zagreb index, second Zagreb index, root-indices, octane isomers, discrimination power
Published in DKUM: 19.12.2024; Views: 0; Downloads: 7
Full text (322,83 KB)
This document has many files! More... |
