BZPEER

preprint2025arXiv

Revisiting $d$ -distance (independent) domination in trees and in bipartite graphs

The $d$ -distance $p$ -packing domination number $γ_d^p(G)$ of $G$ is the minimum size of a set of vertices of $G$ which is both a $d$ -distance dominating set and a $p$ -packing. In 1994, Beineke and Henning conjectured that if $d\ge 1$ and $T$ is a tree of order $n \geq d+1$ , then $γ_d^1(T) \leq \frac{n}{d+1}$ . They supported the conjecture by proving it for $d\in \{1,2,3\}$ . In this paper, it is proved that $γ_d^1(G) \leq \frac{n}{d+1}$ holds for any bipartite graph $G$ of order $n \geq d+1$ , and any $d\ge 1$ . Trees $T$ for which $γ_d^1(T) = \frac{n}{d+1}$ holds are characterized. It is also proved that if $T$ has $\ell$ leaves, then $γ_d^1(T) \leq \frac{n-\ell}{d}$ (provided that $n-\ell \geq d$ ), and $γ_d^1(T) \leq \frac{n+\ell}{d+2}$ (provided that $n\geq d$ ). The latter result extends Favaron's theorem from 1992 asserting that $γ_1^1(T) \leq \frac{n+\ell}{3}$ . In both cases, trees that attain the equality are characterized and relevant conclusions for the $d$ -distance domination number of trees derived.

preprint2025arXiv

Three algorithmic approaches to the general position problem

If $G$ is a graph, then $X\subseteq V(G)$ is a general position set if for every two vertices $v,u\in X$ and every shortest $(u,v)$ -path $P$ , it holds that no inner vertex of $P$ lies in $X$ . In this note we propose three algorithms to compute a largest general position set in $G$ : an integer linear programming algorithm, a genetic algorithm, and a simulated annealing algorithm. These approaches are supported by examples from different areas of graph theory.

preprint2024arXiv

Lower General Position Sets in Graphs

A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$ . In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower general position number} $\gp ^-(G)$ of $G$ , which is the number of vertices in a smallest maximal general position set of $G$ . We show that ${\rm gp}^-(G) = 2$ if and only if $G$ contains a universal line and determine this number for several classes of graphs, including Kneser graphs $K(n,2)$ , line graphs of complete graphs, and Cartesian and direct products of two complete graphs. We also prove several realisation results involving the lower general position number, the general position number and the geodetic number, and compare it with the lower version of the monophonic position number. We provide a sharp upper bound on the size of graphs with given lower general position number. Finally we demonstrate that the decision version of the lower general position problem is NP-complete.

preprint2024arXiv

Mutual-visibility problems on graphs of diameter two

The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$ -path $P$ so that all internal vertices of $P$ are not in $S$ . This is also said as $x,y$ are visible with respect to $S$ , or $S$ -visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside $S$ . Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters. The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankievicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Turán problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.

preprint2022arXiv

Extremal results on stepwise transmission irregular graphs

The transmission ${\rm Tr}_G(v)$ of a vertex $v$ of a connected graph $G$ is the sum of distances between $v$ and all other vertices in $G$ . $G$ is a stepwise transmission irregular (STI) graph if $|{\rm Tr}_G(u) - {\rm Tr}_G(v)| =1$ holds for each edge $uv \in E(G)$ . In this paper, extremal results on STI graphs with respect to the size and different metric properties are proved. Two extremal families appear in all the cases, balanced complete bipartite graphs of odd order and the so called odd hatted cycles.

preprint2022arXiv

Relating the total domination number and the annihilation number for quasi-trees and some composite graphs

The total domination number $γ_{t}(G)$ of a graph $G$ is the cardinality of a smallest set $D\subseteq V(G)$ such that each vertex of $G$ has a neighbor in $D$ . The annihilation number $a(G)$ of $G$ is the largest integer $k$ such that there exist $k$ different vertices in $G$ with the degree sum at most $m(G)$ . It is conjectured that $γ_{t}(G)\leq a(G)+1$ holds for every nontrivial connected graph $G$ . The conjecture has been proved for graphs with minimum degree at least $3$ , trees, certain tree-like graphs, block graphs, and cactus graphs. In the main result of this paper it is proved that the conjecture holds for quasi-trees. The conjecture is verified also for some graph constructions including bijection graphs, Mycielskians, and the newly introduced universally-identifying graphs.

preprint2022arXiv

Thresholds for the monochromatic clique transversal game

We study a recently introduced two-person combinatorial game, the $(a,b)$ -monochromatic clique transversal game which is played by Alice and Bob on a graph $G$ . As we observe, this game is equivalent to the $(b,a)$ -biased Maker-Breaker game played on the clique-hypergraph of $G$ . Our main results concern the threshold bias $a_1(G)$ that is the smallest integer $a$ such that Alice can win in the $(a,1)$ -monochromatic clique transversal game on $G$ if she is the first to play. Among other results, we determine the possible values of $a_1(G)$ for the disjoint union of graphs, prove a formula for $a_1(G)$ if $G$ is triangle-free, and obtain the exact values of $a_1(C_n \,\square\, C_m)$ , $a_1(C_n \,\square\, P_m)$ , and $a_1(P_n \,\square\, P_m)$ for all possible pairs $(n,m)$ .

preprint2021arXiv

On the Relation Between Wiener Index and Eccentricity of a Graph

The relation between the Wiener index $W(G)$ and the eccentricity $\varepsilon(G)$ of a graph $G$ is studied. Lower and upper bounds on $W(G)$ in terms of $\varepsilon(G)$ are proved and extremal graphs characterized. A Nordhaus-Gaddum type result on $W(G)$ involving $\varepsilon(G)$ is given. A sharp upper bound on the Wiener index of a tree in terms of its eccentricity is proved. It is shown that in the class of trees of the same order, the difference $W(T) - \varepsilon(T)$ is minimized on caterpillars. An exact formula for $W(T) - \varepsilon(T)$ in terms of the radius of a tree $T$ is obtained. A lower bound on the eccentricity of a tree in terms of its radius is also given. Two conjectures are proposed. The first asserts that the difference $W(G) - \varepsilon(G)$ does not increase after contracting an edge of $G$ . The second conjecture asserts that the difference between the Wiener index of a graph and its eccentricity is largest on paths.

preprint2021arXiv

Some binary products and integer linear programming for computing $k$ -metric dimension of graphs

Let $G$ be a connected graph. For an ordered set $S=\{v_1,\ldots, v_\ell\}\subseteq V(G)$ , the vector $r_G(v|S) = (d_G(v_1,v), \ldots, d_G(v_\ell,v))$ is called the metric $S$ -representation of $v$ . If for any pair of different vertices $u,v\in V(G)$ , the vectors $r(v|S)$ and $r(u|S)$ differ in at least $k$ positions, then $S$ is a $k$ -metric generator for $G$ . A smallest $k$ -metric generator for $G$ is a $k$ -{\em metric basis} for $G$ , its cardinality being the $k$ -metric dimension of $G$ . A sharp upper bound and a closed formulae for the $k$ -metric dimension of the hierarchical product of graphs is proved. Also, sharp lower bounds for the $k$ -metric dimension of the splice and link products of graphs are presented. An integer linear programming model for computing the $k$ -metric dimension and a $k$ -metric basis of a given graph is proposed. These results are applied to bound or to compute the $k$ -metric dimension of some classes of graphs that are of interest in mathematical chemistry.

preprint2021arXiv

The domination game played on diameter 2 graphs

Let $γ_g(G)$ be the game domination number of a graph $G$ . It is proved that if ${\rm diam}(G) = 2$ , then $γ_g(G) \le \left\lceil \frac{n(G)}{2} \right\rceil- \left\lfloor \frac{n(G)}{11}\right\rfloor$ . The bound is attained: if ${\rm diam}(G) = 2$ and $n(G) \le 10$ , then $γ_g(G) = \left\lceil \frac{n(G)}{2} \right\rceil$ if and only if $G$ is one of seven sporadic graphs with $n(G)\le 6$ or the Petersen graph, and there are exactly ten graphs of diameter $2$ and order $11$ that attain the bound.

preprint2021arXiv

The geodesic-transversal problem

A maximal geodesic in a graph is a geodesic (alias shortest path) which is not a subpath of a longer geodesic. The geodesic-transversal problem in a graph $G$ is introduced as the task to find a smallest set $S$ of vertices of $G$ such that each maximal geodesic has at least one vertex in $S$ . The minimum cardinality of such a set is the geodesic-transversal number ${\rm gt}(G)$ of $G$ . It is proved that ${\rm gt}(G) = 1$ if and only if $G$ is a subdivided star and that the geodesic-transversal problem is NP-complete. Fast algorithms to determine the geodesic-transversal number of trees and of spread cactus graphs are designed, respectively.

preprint2020arXiv

Constructing new families of transmission irregular graphs

The transmission of a vertex $v$ of a graph $G$ is the sum of distances from $v$ to all the other vertices in $G$ . A graph is transmission irregular if all of its vertices have pairwise different transmissions. A starlike tree $T(k_1,\ldots,k_t)$ is a tree obtained by attaching to an isolated vertex $t$ pendant paths of lengths $k_1,\ldots,k_t$ , respectively. It is proved that if a starlike tree $T(a,a+1,\ldots,a+k)$ , $k\ge 2$ , is of odd order, then it is transmission irregular. $T(1,2,\ldots,\ell)$ , $\ell \ge 3$ , is transmission irregular if and only if $\ell \notin \{r^2 + 1:\ r\ge 2\}$ . Additional infinite families among the starlike trees and bi-starlike trees are determined. Transmission irregular unicyclic infinite families are also presented, in particular, the line graph of $T(a,a+1,a+2)$ , $a\ge 2$ , is transmission irregular if and only if $a$ is even.

preprint2020arXiv

Dominated and dominator colorings over (edge) corona and hierarchical products

Dominator coloring of a graph is a proper (vertex) coloring with the property that every vertex is either alone in its color class or adjacent to all vertices of at least one color class. A dominated coloring of a graph is a proper coloring such that every color class is dominated with at least one vertex. The dominator chromatic number of corona products and of edge corona products is determined. Sharp lower and upper bounds are given for the dominated chromatic number of edge corona products. The dominator chromatic number of hierarchical products is bounded from above and the dominated chromatic number of hierarchical products with two factors determined. An application of dominated colorings in genetic networks is also proposed.

preprint2020arXiv

Edge metric dimensions via hierarchical product and integer linear programming

If $S=\{v_1,\ldots, v_k\}$ is an ordered subset of vertices of a connected graph $G$ and $e$ is an edge of $G$ , then the vector $r_G(e|S) = (d_G(v_1,e), \ldots, d_G(v_k,e))$ is the edge metric $S$ -representation of $e$ . If the vertices of $G$ have pairwise different edge metric $S$ -representations, then $S$ is an edge metric generator for $G$ . The cardinality of a smallest edge metric generator is the edge metric dimension ${\rm edim}(G)$ of $G$ . A general sharp upper bound on the edge metric dimension of hierarchical products $G(U)\sqcap H$ is proved. Exact formula is derived for the case when $|U| = 1$ . An integer linear programming model for computing the edge metric dimension is proposed. Several examples are provided which demonstrate how these two methods can be applied to obtain the edge metric dimensions of some applicable graphs.

preprint2020arXiv

Maker-Breaker resolving game

A set of vertices $W$ of a graph $G$ is a resolving set if every vertex of $G$ is uniquely determined by its vector of distances to $W$ . In this paper, the Maker-Breaker resolving game is introduced. The game is played on a graph $G$ by Resolver and Spoiler who alternately select a vertex of $G$ not yet chosen. Resolver wins if at some point the vertices chosen by him form a resolving set of $G$ , whereas Spoiler wins if the Resolver cannot form a resolving set of $G$ . The outcome of the game is denoted by $o(G)$ and $R_{\rm MB}(G)$ (resp. $S_{\rm MB}(G)$ ) denotes the minimum number of moves of Resolver (resp. Spoiler) to win when Resolver has the first move. The corresponding invariants for the game when Spoiler has the first move are denoted by $R'_{\rm MB}(G)$ and $S'_{\rm MB}(G)$ . Invariants $R_{\rm MB}(G)$ , $R'_{\rm MB}(G)$ , $S_{\rm MB}(G)$ , and $S'_{\rm MB}(G)$ are compared among themselves and with the metric dimension ${\rm dim}(G)$ . A large class of graphs $G$ is constructed for which $R_{\rm MB}(G) > {\rm dim}(G)$ holds. The effect of twin equivalence classes and pairing resolving sets on the Maker-Breaker resolving game is described. As an application $o(G)$ , as well as $R_{\rm MB}(G)$ and $R'_{\rm MB}(G)$ (or $S_{\rm MB}(G)$ and $S'_{\rm MB}(G)$ ), are determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.

preprint2020arXiv

On $\ell$ -distance balanced product graphs

A graph $G$ is $\ell$ -distance-balanced if for each pair of vertices $x$ and $y$ at distance $\ell$ in $G$ , the number of vertices closer to $x$ than to $y$ is equal to the number of vertices closer to $y$ than to $x$ . A complete characterization of $\ell$ -distance-balanced corona products is given and a characterization of lexicographic products for $\ell \ge 3$ , thus complementing known results for $\ell\in \{1,2\}$ and correcting an earlier related assertion. A sufficient condition on $H$ which guarantees that $K_n \,\square\, H$ is $\ell$ -distance-balanced is given and it is proved that if $K_n \,\square\, H$ is $\ell$ -distance-balanced, then $H$ is an $\ell$ -distance-balanced graph. A known characterization of $1$ -distance-balanced graphs is extended to $\ell$ -distance-balanced graphs, again correcting an earlier claimed assertion.

preprint2020arXiv

On Rall's $1/2$ -conjecture on the domination game

The $1/2$ -conjecture on the domination game asserts that if $G$ is a traceable graph, then the game domination number $γ_g(G)$ of $G$ is at most $\left\lceil \frac{n(G)}{2} \right\rceil$ . A traceable graph is a $1/2$ -graph if $γ_g(G) = \left\lceil \frac{n(G)}{2} \right\rceil$ holds. It is proved that the so-called hatted cycles are $1/2$ -graphs and that unicyclic graphs fulfill the $1/2$ -conjecture. Several additional families of graphs that support the conjecture are determined and computer experiments related to the conjecture described.

preprint2020arXiv

On the difference between the eccentric connectivity index and eccentric distance sum of graphs

The eccentric connectivity index of a graph $G$ is $ξ^c(G) = \sum_{v \in V(G)}\varepsilon(v)°(v)$ , and the eccentric distance sum is $ξ^d(G) = \sum_{v \in V(G)}\varepsilon(v)D(v)$ , where $\varepsilon(v)$ is the eccentricity of $v$ , and $D(v)$ the sum of distances between $v$ and the other vertices. A lower and an upper bound on $ξ^d(G) - ξ^c(G)$ is given for an arbitrary graph $G$ . Regular graphs with diameter at most $2$ and joins of cocktail-party graphs with complete graphs form the graphs that attain the two equalities, respectively. Sharp lower and upper bounds on $ξ^d(T) - ξ^c(T)$ are given for arbitrary trees. Sharp lower and upper bounds on $ξ^d(G)+ξ^c(G)$ for arbitrary graphs $G$ are also given, and a sharp lower bound on $ξ^d(G)$ for graphs $G$ with a given radius is proved.

preprint2020arXiv

On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

It was recently pointed out that certain SiO $_2$ layer structures and SiO $_2$ nanotubes can be described as full subdivisions aka subdivision graphs of partial cubes. A key tool for analyzing distance-based topological indices in molecular graphs is the Djoković-Winkler relation $Θ$ and its transitive closure $Θ^\ast$ . In this paper we study the behavior of $Θ$ and $Θ^\ast$ with respect to full subdivisions. We apply our results to describe $Θ^\ast$ in full subdivisions of fullerenes, plane triangulations, and chordal graphs.

preprint2020arXiv

On the general position number of complementary prisms

The general position number ${\rm gp}(G)$ of a graph $G$ is the cardinality of a largest set of vertices $S$ such that no element of $S$ lies on a geodesic between two other elements of $S$ . The complementary prism $G\overline{G}$ of $G$ is the graph formed from the disjoint union of $G$ and its complement $\overline{G}$ by adding the edges of a perfect matching between them. It is proved that ${\rm gp}(G\overline{G})\le n(G) + 1$ if $G$ is connected and ${\rm gp}(G\overline{G})\le n(G)$ if $G$ is disconnected. Graphs $G$ for which ${\rm gp}(G\overline{G}) = n(G) + 1$ holds, provided that both $G$ and $\overline{G}$ are connected, are characterized. A sharp lower bound on ${\rm gp}(G\overline{G})$ is proved. If $G$ is a connected bipartite graph or a split graph then ${\rm gp}(G\overline{G})\in \{n(G), n(G)+1\}$ . Connected bipartite graphs and block graphs for which ${\rm gp}(G\overline{G})=n(G)+1$ holds are characterized. A family of block graphs is constructed in which the ${\rm gp}$ -number of their complementary prisms is arbitrary smaller than their order.

preprint2020arXiv

Some extremal results on the chromatic-stability index

The $χ$ -stability index ${\rm es}_χ(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$ . In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$ -regular ( $k\le 5$ ) graphs $G$ with ${\rm es}_χ(G) = 1$ does not extend to $k\ge 6$ . Graphs $G$ with $χ(G)=3$ for which ${\rm es}_χ(G)+{\rm es}_χ(\overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${\rm es}_χ(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $n\equiv 2 \pmod 3$ and $χ(G)=3$ .

preprint2020arXiv

The general position number of integer lattices

The general position number ${\rm gp}(G)$ of a connected graph $G$ is the cardinality of a largest set $S$ of vertices such that no three pairwise distinct vertices from $S$ lie on a common geodesic. The $n$ -dimensional grid graph $\pn$ is the Cartesian product of $n$ copies of the two-way infinite path $P_\infty$ . It is proved that if $n\in {\mathbb N}$ , then ${\rm gp}({P_\infty^n}) = 2^{2^{n-1}}$ . The result was earlier known only for $n\in \{1,2\}$ and partially for $n=3$ .

preprint2020arXiv

The Steiner $k$ -eccentricity on trees

We study the Steiner $k$ -eccentricity on trees, which generalizes the previous one in the paper [X.~Li, G.~Yu, S.~Klavžar, On the average Steiner 3-eccentricity of trees, arXiv:2005.10319, 2020]. To support the algorithm, we achieve much stronger properties for the Steiner $k$ -ecc tree than that in the previous paper. Based on this, a linear time algorithm is devised to calculate the Steiner $k$ -eccentricity of a vertex in a tree. On the other hand, the lower and upper bounds of the average Steiner $k$ -eccentricity index of a tree on order $n$ are established based on a novel technique which is quite different from that in the previous paper but much easier to follow.

preprint2016arXiv

(Total) Domination in Prisms

With the aid of hypergraph transversals it is proved that $γ_t(Q_{n+1}) = 2γ(Q_n)$ , where $γ_t(G)$ and $γ(G)$ denote the total domination number and the domination number of $G$ , respectively, and $Q_n$ is the $n$ -dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then $γ_t(G \square K_2) = 2γ(G)$ . Further, we show that the bipartite condition is essential by constructing, for any $k \ge 1$ , a (non-bipartite) graph $G$ such that $γ_t (G \square K_2 ) = 2γ(G) - k$ . Along the way several domination-type identities for hypercubes are also obtained.

preprint2016arXiv

Complexity of the Game Domination Problem

The game domination number is a graph invariant that arises from a game, which is related to graph domination in a similar way as the game chromatic number is related to graph coloring. In this paper we show that verifying whether the game domination number of a graph is bounded by a given integer is PSPACE-complete. This contrasts the situation of the game coloring problem whose complexity is still unknown.

preprint2016arXiv

Dominating sequences in grid-like and toroidal graphs

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$ . In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.

preprint2016arXiv

On the structure of dominating graphs

The $k$ -dominating graph $D_k(G)$ of a graph $G$ is defined on the vertex set consisting of dominating sets of $G$ with cardinality at most $k$ , two such sets being adjacent if they differ by either adding or deleting a single vertex. A graph is a dominating graph if it is isomorphic to $D_k(G)$ for some graph $G$ and some positive integer $k$ . Answering a question of Haas and Seyffarth for graphs without isolates, it is proved that if $G$ is such a graph of order $n\ge 2$ and with $G\cong D_k(G)$ , then $k=2$ and $G=K_{1,n-1}$ for some $n\ge 4$ . It is also proved that for a given $r$ there exist only a finite number of $r$ -regular, connected dominating graphs of connected graphs. In particular, $C_6$ and $C_8$ are the only dominating graphs in the class of cycles. Some results on the order of dominating graphs are also obtained.

preprint2016arXiv

Packing chromatic number under local changes in a graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$ -vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$ . It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$ , thus answering an open problem from [Gastineau, Togni, $S$ -packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$ , then $\left\lfloor χ_ρ(G)/2 \right\rfloor +1 \le χ_ρ(S_e(G)) \le χ_ρ(G)+1$ .

preprint2016arXiv

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $Π_1,\ldots,Π_k$ , where $Π_i$ , $i\in [k]$ , is an $i$ -packing. The following conjecture is posed and studied: if $G$ is a subcubic graph, then $χ_ρ(S(G))\le 5$ , where $S(G)$ is the subdivision of $G$ . The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if $G$ is a generalized prism of a cycle, then $G$ is $(1,1,2,2)$ -colorable if and only if $G$ is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two $n$ -cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.

preprint2014arXiv

Improved upper bounds on the domination number of graphs with minimum degree at least five

An algorithmic upper bound on the domination number $γ$ of graphs in terms of the order $n$ and the minimum degree $δ$ is proved. It is demonstrated that the bound improves best previous bounds for any $5\le δ\le 50$ . In particular, for $δ=5$ , Xing et al.\ proved in 2006 that $γ\le 5n/14 < 0.3572 n$ . This bound is improved to $0.3440 n$ . For $δ=6$ , Clark et al.\ in 1998 established $γ<0.3377 n$ , while Biró et al. recently improved it to $γ<0.3340 n$ . Here the bound is further improved to $γ< 0.3159 n$ . For $δ=7$ , the best earlier bound $0.3 088 n$ is improved to $γ< 0.2927 n$ .

preprint2014arXiv

M-Polynomial and Degree-Based Topological Indices

Let $G$ be a graph and let $m_{ij}(G)$ , $i,j\ge 1$ , be the number of edges $uv$ of $G$ such that $\{d_v(G), d_u(G)\} = \{i,j\}$ . The {\em $M$ -polynomial} of $G$ is introduced with $\displaystyle{M(G;x,y) = \sum_{i\le j} m_{ij}(G)x^iy^j}$ . It is shown that degree-based topological indices can be routinely computed from the polynomial, thus reducing the problem of their determination in each particular case to the single problem of determining the $M$ -polynomial. The new approach is also illustrated with examples.

preprint2014arXiv

On Isomorphism Classes of Generalized Fibonacci Cubes

The generalized Fibonacci cube $Q_d(f)$ is the subgraph of the $d$ -cube $Q_d$ induced on the set of all strings of length $d$ that do not contain $f$ as a substring. It is proved that if $Q_d(f) \cong Q_d(f')$ then $|f|=|f'|$ . The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings $f, f'$ such that $Q_d(f) \cong Q_d(f')$ , where $|f| \ge \frac{2}{3}(d+1)$ and $f'$ cannot be obtained from $f$ by its reversal or binary complementation. Strings $f$ and $f'$ with $|f|=|f'|=d-1$ for which $Q_d(f) \cong Q_d(f')$ are characterized.

preprint2014arXiv

Vertex and edge orbits of Fibonacci and Lucas cubes

The Fibonacci cube $Γ_n$ is obtained from the $n$ -cube $Q_n$ by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube $Λ_n$ is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of the sizes of the vertex orbits of $Λ_n$ is $\{k \ge 1;\ k \divides n\} \cup\, \{k \ge 18;\ k \divides 2n\}$, the number of the vertex orbits of $Λ_n$ of size $k$ , where $k$ is odd and divides $n$ , is equal to $\sum_{d\divides k}μ\left(\frac{k}{d}\right) F_{\lfloor \frac{d}{2}\rfloor + 2}$, and the number of the edge orbits of $Λ_n$ is equal to the number of the vertex orbits of $Γ_{n-3}$ . Dihedral transformations of strings and primitive strings are essential tools to prove these results.

preprint2013arXiv

Domination game: effect of edge- and vertex-removal

The domination game is played on a graph $G$ by two players, named Dominator and Staller. They alternatively select vertices of $G$ such that each chosen vertex enlarges the set of vertices dominated before the move on it. Dominator's goal is that the game is finished as soon as possible, while Staller wants the game to last as long as possible. It is assumed that both play optimally. Game 1 and Game 2 are variants of the game in which Dominator and Staller has the first move, respectively. The game domination number $γ_g(G)$ , and the Staller-start game domination number $γ_g'(G)$ , is the number of vertices chosen in Game 1 and Game 2, respectively. It is proved that if $e\in E(G)$ , then $|γ_g(G) - γ_g(G-e)| \le 2$ and $|γ_g'(G) - γ_g'(G-e)| \le 2$ , and that each of the possibilities here is realizable by connected graphs $G$ for all values of $γ_g(G)$ and $γ_g'(G)$ larger than 5. For the remaining small values it is either proved that realizations are not possible or realizing examples are provided. It is also proved that if $v\in V(G)$ , then $γ_g(G) - γ_g(G-v) \le 2$ and $γ_g'(G) - γ_g'(G-v) \le 2$ . Possibilities here are again realizable by connected graphs $G$ in almost all the cases, the exceptional values are treated similarly as in the edge-removal case.

preprint2012arXiv

Moore graphs and cycles are extremal graphs for convex cycles

Let $ρ(G)$ denote the number of convex cycles of a simple graph G of order n, size m, and girth 3 <= g <=n. It is proved that $ρ(G) \leq \frac{n}{g}(m-n+1)$ and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.

Sandi Klavžar

Research overview

Is this your work?

35 publications

Revisiting ddd-distance (independent) domination in trees and in bipartite graphs

Three algorithmic approaches to the general position problem

Lower General Position Sets in Graphs

Mutual-visibility problems on graphs of diameter two

Extremal results on stepwise transmission irregular graphs

Relating the total domination number and the annihilation number for quasi-trees and some composite graphs

Thresholds for the monochromatic clique transversal game

On the Relation Between Wiener Index and Eccentricity of a Graph

Some binary products and integer linear programming for computing kkk-metric dimension of graphs

The domination game played on diameter 2 graphs

The geodesic-transversal problem

Constructing new families of transmission irregular graphs

Dominated and dominator colorings over (edge) corona and hierarchical products

Edge metric dimensions via hierarchical product and integer linear programming

Maker-Breaker resolving game

On ℓ\ellℓ-distance balanced product graphs

On Rall's 1/21/21/2-conjecture on the domination game

On the difference between the eccentric connectivity index and eccentric distance sum of graphs

On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

On the general position number of complementary prisms

Some extremal results on the chromatic-stability index

The general position number of integer lattices

The Steiner kkk-eccentricity on trees

(Total) Domination in Prisms

Complexity of the Game Domination Problem

Dominating sequences in grid-like and toroidal graphs

On the structure of dominating graphs

Packing chromatic number under local changes in a graph

Packing chromatic number, (1,1,2,2)(1,1,2,2)(1,1,2,2)-colorings, and characterizing the Petersen graph

Improved upper bounds on the domination number of graphs with minimum degree at least five

M-Polynomial and Degree-Based Topological Indices

On Isomorphism Classes of Generalized Fibonacci Cubes

Vertex and edge orbits of Fibonacci and Lucas cubes

Domination game: effect of edge- and vertex-removal

Moore graphs and cycles are extremal graphs for convex cycles

See the researcher in context

Building this map preview

Revisiting $d$ -distance (independent) domination in trees and in bipartite graphs

Some binary products and integer linear programming for computing $k$ -metric dimension of graphs

On $\ell$ -distance balanced product graphs

On Rall's $1/2$ -conjecture on the domination game

The Steiner $k$ -eccentricity on trees

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph