11. Distance formula for direct-co-direct product in the case of disconnected factorsAleksander Kelenc, Iztok Peterin, 2023, izvirni znanstveni članek Povzetek: Direct-co-direct product $G\circledast H$ of graphs $G$ and $H$ is a graph on the vertex set $V(G)\times V(H)$. Two vertices $(g,h)$ and $(g',h')$ are adjacent if $gg'\in E(G)$ and $hh'\in E(H)$ or $gg'\notin E(G)$ and $hh'\notin E(H)$. We show that if at most one factor of $G\circledast H$ is connected, then the distance between two vertices of $G\circledast H$ is bounded by three unless some small number of exceptions. All the exceptions are completely described which yields the distance formula. Ključne besede: direct-co-direct product, distance, eccentricity, disconnected graphs Objavljeno v DiRROS: 19.03.2024; Ogledov: 307; Prenosov: 128 Celotno besedilo (450,88 KB) Gradivo ima več datotek! Več... |
12. A method for computing the edge-Hosoya polynomial with application to phenylenesMartin Knor, Niko Tratnik, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: edge-Hosoya polynomial, graphs, phenylenes Objavljeno v DiRROS: 18.03.2024; Ogledov: 474; Prenosov: 379 Celotno besedilo (530,53 KB) |
13. Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphsSimon Brezovnik, Niko Tratnik, Petra Žigert Pleteršek, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: graph theory, resonance graphs, bipartite graphs Objavljeno v DiRROS: 18.03.2024; Ogledov: 297; Prenosov: 82 Celotno besedilo (433,15 KB) |
14. Zhang-Zhang polynomials of phenylenes and benzenoid graphsNiko Tratnik, 2024, izvirni znanstveni članek Povzetek: 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. Ključne besede: graph theory, resonance graphs, polynomials Objavljeno v DiRROS: 18.03.2024; Ogledov: 268; Prenosov: 99 Celotno besedilo (487,12 KB) |
15. Cubic vertex-transitive graphs admitting automorphisms of large orderPrimož Potočnik, Micael Toledo, 2023, izvirni znanstveni članek Povzetek: 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$. Ključne besede: cubic vertex-transitive graphs, multicirculants, automorphisms of large order Objavljeno v DiRROS: 18.03.2024; Ogledov: 293; Prenosov: 139 Celotno besedilo (929,04 KB) Gradivo ima več datotek! Več... |
16. 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, izvirni znanstveni članek Ključne besede: inverse eigenvalue problem, minimum number of distinct eigenvalues, borderings, joins of graphs, paths, cycles, hypercubes Objavljeno v DiRROS: 18.03.2024; Ogledov: 343; Prenosov: 164 Celotno besedilo (485,46 KB) Gradivo ima več datotek! Več... |
17. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number Objavljeno v DiRROS: 14.03.2024; Ogledov: 339; Prenosov: 140 Celotno besedilo (453,39 KB) Gradivo ima več datotek! Več... |
18. Outerplane bipartite graphs with isomorphic resonance graphsSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2024, izvirni znanstveni članek Povzetek: 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. Ključne besede: distributive lattice, inner dual, isomorphic resonance graphs, order ideal, 2-connected outerplane bipartite graph Objavljeno v DiRROS: 13.03.2024; Ogledov: 334; Prenosov: 151 Celotno besedilo (452,02 KB) Gradivo ima več datotek! Več... |
19. On the structure of consistent cycles in cubic symmetric graphsKlavdija Kutnar, Dragan Marušič, Štefko Miklavič, Primož Šparl, 2024, izvirni znanstveni članek Ključne besede: 1/2-consistent cycles, automorphisms, consistent cycles, cubic symmetric graphs, shunt, s-regular graphs Objavljeno v DiRROS: 13.03.2024; Ogledov: 287; Prenosov: 158 Celotno besedilo (1,02 MB) Gradivo ima več datotek! Več... |
20. General position polynomialsVesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, izvirni znanstveni članek Povzetek: 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. Ključne besede: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs Objavljeno v DiRROS: 28.02.2024; Ogledov: 372; Prenosov: 199 Celotno besedilo (384,07 KB) Gradivo ima več datotek! Več... |