1. Injective coloring of graphs revisitedBoštjan Brešar, Babak Samadi, Ismael G. Yero, 2023, izvirni znanstveni članek Povzetek: An open packing in a graph $G$ is a set $S$ of vertices in $G$ such that no two vertices in $S$ have a common neighbor in $G$. The injective chromatic number $\chi_i(G)$ of $G$ is the smallest number of colors assigned to vertices of ▫$G$▫ such that each color class is an open packing. Alternatively, the injective chromatic number of $G$ is the chromatic number of the two-step graph of $G$, which is the graph with the same vertex set as $G$ in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that $\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$ holds for any connected graph $G$ of order $n\ge 2$, size $m$, and the open packing number ${\rho^{o}}$, and characterize the class of graphs attaining the bound. Regarding the well known bound $\chi_i(G)\ge \Delta(G)$, we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which $\chi_i(G)$ equals the cardinality of a largest clique of the two-step graph of $G$. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property.
Ključne besede: two-step graph of a graph, injective coloring, open packing, hypercubes
Objavljeno v DiRROS: 09.04.2024; Ogledov: 65; Prenosov: 51
 Celotno besedilo (460,72 KB)
Gradivo ima več datotek! Več... |
2. The core of a vertex-transitive complementary prismMarko Orel, 2023, izvirni znanstveni članek Povzetek: The complementary prism $\Gamma \overline{\Gamma}$ is obtained from the union of a graph $\Gamma$ and its complement $\overline{\Gamma}$ where each pair of identical vertices in $\Gamma$ and $\overline{\Gamma}$ is joined by an edge. It generalizes the Petersen graph, which is the complementary prism of the pentagon. The core of a vertex-transitive complementary prism is studied. In particular, it is shown that a vertex-transitive complementary prism $\Gamma \overline{\Gamma}$ is a core, i.e. all its endomorphisms are automorphisms, whenever $\Gamma$ is a core or its core is a complete graph.
Ključne besede: graph homomorphism, complementary prism, self-complementary graph, vertex-transitive graph, core
Objavljeno v DiRROS: 09.04.2024; Ogledov: 57; Prenosov: 32
Celotno besedilo (309,75 KB)
Gradivo ima več datotek! Več... |
3. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, izvirni znanstveni članek Povzetek: In this paper, generalized Pell graphs $\Pi_{n,k}$, $k\ge 2$, are introduced. The special case of $k=2$ are the Pell graphs $\Pi_{n}$ defined earlier by Munarini. Several metric, enumerative, and structural properties of these graphs are established. The generating function of the number of edges of $\Pi_{n,k}$ and the generating function of its cube polynomial are determined. The center of $\Pi_{n,k}$ is explicitly described; if $k$ is even, then it induces the Fibonacci cube $\Gamma_{n}$. It is also shown that $\Pi_{n,k}$ is a median graph, and that $\Pi_{n,k}$ embeds into a Fibonacci cube.
Ključne besede: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence
Objavljeno v DiRROS: 08.04.2024; Ogledov: 83; Prenosov: 35
Celotno besedilo (345,71 KB)
Gradivo ima več datotek! Več... |
4. Generalized cut method for computing Szeged-like polynomials with applications to polyphenyls and carbon nanoconesSimon Brezovnik, Niko Tratnik, 2023, izvirni znanstveni članek Povzetek: 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 DiRROS: 20.03.2024; Ogledov: 101; Prenosov: 30
Celotno besedilo (599,00 KB) |
5. Orientable domination in product-like graphsSarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, izvirni znanstveni članek Povzetek: The orientable domination number, ${\rm DOM}(G)$, of a graph $G$ is the largest domination number over all orientations of $G$. In this paper, ${\rm DOM}$ is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. from 1996 is extended by establishing the values of ${\rm DOM}(K_{n_1,n_2,n_3})$ for arbitrary positive integers $n_1,n_2$ and $n_3$. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in [Domination in digraphs and their direct and Cartesian products, J. Graph Theory 99 (2022) 359-377].
Ključne besede: digraph, domination, orientable domination number, packing, graph product, corona graph
Objavljeno v DiRROS: 20.03.2024; Ogledov: 109; Prenosov: 52
Celotno besedilo (366,61 KB)
Gradivo ima več datotek! Več... |
6. The Sierpiński product of graphsJurij Kovič, Tomaž Pisanski, Sara Sabrina Zemljič, Arjana Žitnik, 2023, izvirni znanstveni članek Povzetek: In this paper we introduce a product-like operation that generalizes the construction of the generalized Sierpiński graphs. Let $G$, $H$ be graphs and let $f: V(G) \to V(H)$ be a function. Then the Sierpiński product of graphs $G$ and $H$ with respect to $f$, denoted by $G\otimes_f H$, is defined as the graph on the vertex set $V(G) \times V(H)$, consisting of $|V(G)|$ copies of $H$; for every edge $\{g, g'\}$ of $G$ there is an edge between copies $gH$ and $g'H$ of form $\{(g, f(g'), (g', f(g))\}$. Some basic properties of the Sierpiński product are presented. In particular, we show that the graph $G\otimes_f H$ is connected if and only if both graphs $G$ and $H$ are connected and we present some conditions that $G, \, H$ must fulfill for $G\otimes_f H$ to be planar. As for symmetry properties, we show which automorphisms of $G$ and $H$ extend to automorphisms of $G\otimes_f H$. In several cases we can also describe the whole automorphism group of the graph $G\otimes_f H$. Finally, we show how to extend the Sierpiński product to multiple factors in a natural way. By applying this operation $n$ times to the same graph we obtain an alternative approach to the well-known $n$-th generalized Sierpiński graph.
Ključne besede: Sierpiński graphs, graph products, connectivity, planarity, symmetry
Objavljeno v DiRROS: 19.03.2024; Ogledov: 127; Prenosov: 48
Celotno besedilo (533,30 KB)
Gradivo ima več datotek! Več... |
7. The core of a vertex transitive complementary prism of a lexicographic productMarko Orel, 2023, izvirni znanstveni članek Povzetek: The complementary prism of a graph $\Gamma$ is the graph $\Gamma \overline{\Gamma}$, which is formed from the union of $\Gamma$ and its complement $\overline{\Gamma}$ by adding an edge between each pair of identical vertices in $\Gamma$ and $\overline{\Gamma}$. Vertex-transitive self-complementary graphs provide vertex-transitive complementary prisms. It was recently proved by the author that $\Gamma \overline{\Gamma}$ is a core, i.e. all its endomorphisms are automorphisms, whenever $\Gamma$ is vertex-transitive, self-complementary, and either $\Gamma$ is a core or its core is a complete graph. In this paper the same conclusion is obtained for some other classes of vertex-transitive self-complementary graphs that can be decomposed as a lexicographic product $\Gamma = \Gamma_1 [\Gamma_2]$. In the process some new results aboutthe homomorphisms of a lexicographic product are obtained.
Ključne besede: graph homomorphism, core, complementary prism, self-complementary graph, vertex-transitive graph, lexicographic product
Objavljeno v DiRROS: 19.03.2024; Ogledov: 71; Prenosov: 42
Celotno besedilo (411,68 KB)
Gradivo ima več datotek! Več... |
8. How to compute the M-polynomial of (chemical) graphsEmeric Deutsch, Sandi Klavžar, Gašper Domen Romih, 2023, izvirni znanstveni članek Povzetek: Let $G$ be a graph and let $m_{i,j}(G)$, $i,j\ge 1$, be the number of edges $uv$ of ▫$G$▫ such that $\{d_v(G), d_u(G)\} = \{i,j\}$. The M-polynomial of $G$ is $M(G;x,y) = \sum_{i\le j} m_{i,j}(G)x^iy^j$. A general method for calculating the M-polynomials for arbitrary graph families is presented. The method is further developed for the case where the vertices of a graph have degrees 2 and $p$, where $p\ge 3$, and further for such planar graphs. The method is illustrated on families of chemical graphs.
Ključne besede: M-polynomial, chemical graph, planar graph
Objavljeno v DiRROS: 18.03.2024; Ogledov: 82; Prenosov: 33
Celotno besedilo (376,13 KB) |
9. 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: 76; Prenosov: 31
Celotno besedilo (433,15 KB) |
10. 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: 86; Prenosov: 35
Celotno besedilo (487,12 KB) |
