11. 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: 113; Downloads: 36
 Full text (433,15 KB) |
12. 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: 120; Downloads: 40
Full text (487,12 KB) |
13. 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: 110; Downloads: 55
Full text (929,04 KB)
This document has many files! More... |
14. 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: 141; Downloads: 92
Full text (485,46 KB)
This document has many files! More... |
15. 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: 129; Downloads: 65
Full text (453,39 KB)
This document has many files! More... |
16. 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: 125; Downloads: 66
Full text (452,02 KB)
This document has many files! More... |
17. 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: 136; Downloads: 65
Full text (1,02 MB)
This document has many files! More... |
18. 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: 140; Downloads: 95
Full text (384,07 KB)
This document has many files! More... |
19. 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: 205; Downloads: 77
Full text (573,20 KB)
This document has many files! More... |
20. Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar, Eva Zmazek, 2024, original scientific article Abstract: A set of vertices $X$ of a graph $G$ is a strong edge geodetic set if to any pair of vertices from $X$ we can assign one (or zero) shortest path between them such that every edge of $G$ is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of $G$ is the strong edge geodetic number ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature.
Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
Published in DiRROS: 19.02.2024; Views: 171; Downloads: 69
Full text (430,75 KB)
This document has many files! More... |
