11. A method for computing the edge-Hosoya polynomial with application to phenylenesMartin Knor, Niko Tratnik, 2023, original scientific article Abstract: The edge-Hosoya polynomial of a graph is the edge version of the famous Hosoya polynomial. Therefore, the edge-Hosoya polynomial counts the number of (unordered) pairs of edges at distance $k \ge 0$ in a given graph. It is well known that this polynomial is closely related to the edge-Wiener index and the edge-hyper-Wiener index. As the main result of this paper, we greatly generalize an earlier result by providing a method for calculating the edge-Hosoya polynomial of a graph $G$ which is obtained by identifying two edges of connected bipartite graphs $G_1$ and $G_2$. To show how the main theorem can be used, we apply it to phenylene chains. In particular, we present the recurrence relations and a linear time algorithm for calculating the edge-Hosoya polynomial of any phenylene chain. As a consequence, closed formula for the edge-Hosoya polynomial of linear phenylene chains is derived. Keywords: edge-Hosoya polynomial, graphs, phenylenes Published in DiRROS: 18.03.2024; Views: 345; Downloads: 335 Full text (530,53 KB) |
12. Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphsSimon Brezovnik, Niko Tratnik, Petra Žigert Pleteršek, 2023, original scientific article Abstract: The aim of this paper is to investigate resonance graphs of $2$-connected outerplane bipartite graphs, which include various families of molecular graphs. Firstly, we present an algorithm for a binary coding of perfect matchings of these graphs. Further, $2$-connected outerplane bipartite graphs with isomorphic resonance graphs are considered. In particular, it is shown that if two $2$-connected outerplane bipartite graphs are evenly homeomorphic, then its resonance graphs are isomorphic. Moreover, we prove that for any $2$-connected outerplane bipartite graph $G$ there exists a catacondensed even ring systems $H$ such that the resonance graphs of $G$ and $H$ are isomorphic. We conclude with the characterization of $2$-connected outerplane bipartite graphs whose resonance graphs are daisy cubes. Keywords: graph theory, resonance graphs, bipartite graphs Published in DiRROS: 18.03.2024; Views: 162; Downloads: 47 Full text (433,15 KB) |
13. Zhang-Zhang polynomials of phenylenes and benzenoid graphsNiko Tratnik, 2024, original scientific article Abstract: The aim of this paper is to study some variations of the Zhang-Zhang polynomial for phenylenes, which can be obtained as special cases of the multivariable Zhang-Zhang polynomial. Firstly, we prove the equality between the first Zhang-Zhang polynomial of a phenylene and the generalized Zhang-Zhang polynomial of some benzenoid graph, which enables us to prove also the equality between the first Zhang-Zhang polynomial and the generalized cube polynomial of the resonance graph. Next, some results on the roots of the second Zhang-Zhang polynomial of phenylenes are provided and another expression for this polynomial is established. Finally, we give structural interpretation for (partial) derivatives of different Zhang-Zhang polynomials. Keywords: graph theory, resonance graphs, polynomials Published in DiRROS: 18.03.2024; Views: 165; Downloads: 58 Full text (487,12 KB) |
14. Cubic vertex-transitive graphs admitting automorphisms of large orderPrimož Potočnik, Micael Toledo, 2023, original scientific article Abstract: A connected graph of order $n$ admitting a semiregular automorphism of order $n/k$ is called a $k$-multicirculant. Highly symmetric multicirculants of small valency have been extensively studied, and several classification results exist for cubic vertex- and arc-transitive multicirculants. In this paper, we study the broader class of cubic vertex-transitive graphs of order $n$ admitting an automorphism of order $n/3$ or larger that may not be semiregular. In particular, we show that any such graph is either a $k$-multicirculant for some $k \le 3$, or it belongs to an infinite family of graphs of girth $6$. Keywords: cubic vertex-transitive graphs, multicirculants, automorphisms of large order Published in DiRROS: 18.03.2024; Views: 161; Downloads: 70 Full text (929,04 KB) This document has many files! More... |
15. Bordering of symmetric matrices and an application to the minimum number of distinct eigenvalues for the join of graphsAida Abiad, Shaun M. Fallat, Mark Kempton, Rupert H. Levene, Polona Oblak, Helena Šmigoc, Michael Tait, Kevin N. Vander Meulen, 2023, original scientific article Keywords: inverse eigenvalue problem, minimum number of distinct eigenvalues, borderings, joins of graphs, paths, cycles, hypercubes Published in DiRROS: 18.03.2024; Views: 182; Downloads: 106 Full text (485,46 KB) This document has many files! More... |
16. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, original scientific article Abstract: Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine. Keywords: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number Published in DiRROS: 14.03.2024; Views: 178; Downloads: 83 Full text (453,39 KB) This document has many files! More... |
17. Outerplane bipartite graphs with isomorphic resonance graphsSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2024, original scientific article Abstract: We present novel results related to isomorphic resonance graphs of 2-connected outerplane bipartite graphs. As the main result, we provide a structure characterization for 2-connected outerplane bipartite graphs with isomorphic resonance graphs. Three additional characterizations are expressed in terms of resonance digraphs, via local structures of inner duals, as well as using distributive lattices on the set of order ideals of posets defined on inner faces of 2-connected outerplane bipartite graphs. Keywords: distributive lattice, inner dual, isomorphic resonance graphs, order ideal, 2-connected outerplane bipartite graph Published in DiRROS: 13.03.2024; Views: 185; Downloads: 86 Full text (452,02 KB) This document has many files! More... |
18. On the structure of consistent cycles in cubic symmetric graphsKlavdija Kutnar, Dragan Marušič, Štefko Miklavič, Primož Šparl, 2024, original scientific article Keywords: 1/2-consistent cycles, automorphisms, consistent cycles, cubic symmetric graphs, shunt, s-regular graphs Published in DiRROS: 13.03.2024; Views: 184; Downloads: 84 Full text (1,02 MB) This document has many files! More... |
19. General position polynomialsVesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, original scientific article Abstract: A subset of vertices of a graph $G$ is a general position set if no triple of vertices from the set lie on a common shortest path in $G$. In this paper we introduce the general position polynomial as $\sum_{i \geq 0} a_i x^i$, where $a_i$ is the number of distinct general position sets of $G$ with cardinality $i$. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs $K(n,2)$, with unimodal general position polynomials are presented. Keywords: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs Published in DiRROS: 28.02.2024; Views: 223; Downloads: 122 Full text (384,07 KB) This document has many files! More... |
20. On orders of automorphisms of vertex-transitive graphsPrimož Potočnik, Micael Toledo, Gabriel Verret, 2024, original scientific article Abstract: In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with $n$ vertices and of valence $d$, $d\le 4$, is at most $c_d n$ where $c_3=1$ and $c_4 = 9$. Whether such a constant $c_d$ exists for valencies larger than $4$ remains an unanswered question. Further, we prove that every automorphism $g$ of a finite connected $3$-valent vertex-transitive graph $\Gamma$, $\Gamma \not\cong K_{3,3}$, has a regular orbit, that is, an orbit of $\langle g \rangle$ of length equal to the order of $g$. Moreover, we prove that in this case either $\Gamma$ belongs to a well understood family of exceptional graphs or at least $5/12$ of the vertices of $\Gamma$ belong to a regular orbit of $g$. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms $C$ of a connected $3$-valent vertex-transitive graph $\Gamma$ in terms of the number of vertices of $\Gamma$ and the length of a longest orbit of $C$. Keywords: graphs, automorphism groups, vertex-transitive, regular orbit, cubic, tetravalent Published in DiRROS: 19.02.2024; Views: 275; Downloads: 100 Full text (573,20 KB) This document has many files! More... |