1. Indicated domination gameBoštjan Brešar, Csilla Bujtás, Vesna Iršič, Douglas F. Rall, Zsolt Tuza, 2024, original scientific article Abstract: Motivated by the success of domination games and by a variation of the coloring game called the indicated coloring game, we introduce a version of domination games called the indicated domination game. It is played on an arbitrary graph $G$ by two players, Dominator and Staller, where Dominator wants to finish the game in as few rounds as possible while Staller wants just the opposite. In each round, Dominator indicates a vertex $u$ of $G$ that has not been dominated by previous selections of Staller, which, by the rules of the game, forces Staller to select a vertex in the closed neighborhood of $u$. The game is finished when all vertices of $G$ become dominated by the vertices selected by Staller. Assuming that both players are playing optimally according to their goals, the number of selected vertices during the game is the indicated domination number, $\gamma_{\rm i}(G)$, of $G$. We prove several bounds on the indicated domination number expressed in terms of other graph invariants. In particular, we find a place of the new graph invariant in the well-known domination chain, by showing that $\gamma_{\rm i}(G)\ge \Gamma(G)$ for all graphs $G$, and by showing that the indicated domination number is incomparable with the game domination number and also with the upper irredundance number. In connection with the trivial upper bound $\gamma_{\rm i}(G)\le n(G)-\delta(G)$, we characterize the class of graphs $G$ attaining the bound provided that $n(G)\ge 2\delta(G)+2$. We prove that in trees, split graphs and grids the indicated domination number equals the independence number. We also find a formula for the indicated domination number of powers of paths, from which we derive that there exist graphs in which the indicated domination number is arbitrarily larger than the upper irredundance number. We provide some partial results supporting the statement that $\gamma_{\rm i}(G)=n(G)/2$ if $G$ is a cubic bipartite graph, and leave this as an open question. Keywords: domination game, indicated coloring, independence number, upper domination number Published in DiRROS: 16.05.2024; Views: 299; Downloads: 236 Full text (367,70 KB) This document has many files! More... |
2. Domination and independence numbers of large 2-crossing-critical graphsVesna Iršič, Maruša Lekše, Miha Pačnik, Petra Podlogar, Martin Praček, 2023, original scientific article Abstract: After 2-crossing-critical graphs were characterized in 2016, their most general subfamily, large 3-connected 2-crossing-critical graphs, has attracted separate attention. This paper presents sharp upper and lower bounds for their domination and independence number. Keywords: crossing-critical graphs, domination number, independence number Published in DiRROS: 09.04.2024; Views: 277; Downloads: 137 Full text (393,09 KB) This document has many files! More... |
3. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, original scientific article Abstract: 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. Keywords: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence Published in DiRROS: 08.04.2024; Views: 327; Downloads: 127 Full text (345,71 KB) This document has many files! More... |
4. 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: 372; Downloads: 199 Full text (384,07 KB) This document has many files! More... |