Source author record

Boštjan Brešar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

13works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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

$S$ -packing colorings of distance graphs $G(\mathbb{Z},\{2,t\})$

Given a graph $G$ and a non-decreasing sequence $S=(a_1,a_2,\ldots)$ of positive integers, the mapping $f:V(G) \rightarrow \{1,\ldots,k\}$ is an $S$ -packing $k$ -coloring of $G$ if for any distinct vertices $u,v\in V(G)$ with $f(u)=f(v)=i$ the distance between $u$ and $v$ in $G$ is greater than $a_i$ . The smallest $k$ such that $G$ has an $S$ -packing $k$ -coloring is the $S$ -packing chromatic number, $χ_S(G)$ , of $G$ . In this paper, we consider the distance graphs $G(\mathbb{Z},\{2,t\})$ , where $t>1$ is an odd integer, which has $\mathbb{Z}$ as its vertex set, and $i,j\in\mathbb{Z}$ are adjacent if $|i-j|\in\{2,t\}$ . We determine the $S$ -packing chromatic numbers of the graphs $G(\mathbb{Z},\{2,t\})$ , where $S$ is any sequence with $a_i\in\{1,2\}$ for all $i$ . In addition, we give lower and upper bounds for the $d$ -distance chromatic numbers of the distance graphs $G(\mathbb{Z},\{2,t\})$ , which in the cases $d\ge t-3$ give the exact values. Implications for the corresponding $S$ -packing chromatic numbers of the circulant graphs are also discussed.

preprint2020arXiv

Domination in digraphs and their products

A dominating (respectively, total dominating) set $S$ of a digraph $D$ is a set of vertices in $D$ such that the union of the closed (respectively, open) out-neighborhoods of vertices in $S$ equals the vertex set of $D$ . The minimum size of a dominating (respectively, total dominating) set of $D$ is the domination (respectively, total domination) number of $D$ , denoted $γ(D)$ (respectively, $γ_t(D)$ ). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of $D$ is denoted by $ρ(D)$ (respectively, $ρ^{\rm o}(D)$ ). We prove that in digraphs whose underlying graphs have girth at least $7$ , the closed (respectively,open) in-neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree $T$ (that is, a digraph whose underlying graph is a tree), $γ_t(T)=ρ^{\rm o}(T)$ and $γ(T)=ρ(T)$ . By using the former equality we then prove that $γ_t(G\times T)=γ_t(G)γ_t(T)$ , where $G$ is any digraph and $T$ is any ditree, each without a source vertex, and $G\times T$ is their direct product. From the equality $γ(T)=ρ(T)$ we derive the bound $γ(G\mathbin{\Box} T)\geγ(G)γ(T)$ , where $G$ is an arbitrary digraph, $T$ an arbitrary ditree and $G\mathbin{\Box} T$ is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs $G$ and $H$ , where $γ(G)\geγ(H)$ , we have $γ(G \mathbin{\Box} H) \ge \frac{1}{2}γ(G)(γ(H) + 1)$ . This inequality is sharp as demonstrated by an infinite family of examples. Ditrees $T$ and digraphs $H$ enjoying $γ(T\mathbin{\Box} H)=γ(T)γ(H)$ are also investigated.

preprint2020arXiv

Packing colorings of subcubic outerplanar graphs

Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$ -packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$ , the distance between $x$ and $y$ is greater than $s_i$ . The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$ -packing coloring of a graph $G$ is called the packing chromatic number of $G$ , denoted $χ_ρ(G)$ . The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all subcubic graphs. In this paper, we prove that the packing chromatic number of any 2-connected bipartite subcubic outerplanar graph is bounded by $7$ . Furthermore, we prove that every subcubic triangle-free outerplanar graph has a $(1,2,2,2)$ -packing coloring, and that there exists a subcubic outerplanar graph with a triangle that does not admit a $(1,2,2,2)$ -packing coloring. In addition, there exists a subcubic triangle-free outerplanar graph that does not admit a $(1,2,2,3)$ -packing coloring. A similar dichotomy is shown for bipartite outerplanar graphs: every such graph admits an $S$ -packing coloring for $S=(1,3,\ldots,3)$ , where $3$ appears $Δ$ times ( $Δ$ being the maximum degree of vertices), and this property does not hold if one of the integers $3$ is replaced by $4$ in the sequence $S$ .

preprint2016arXiv

$1$ -perfectly orientable $K_4$ -minor-free and outerplanar graphs

A graph $G$ is said to be $1$ -perfectly orientable if it has an orientation such that for every vertex $v\in V(G)$ , the out-neighborhood of $v$ in $D$ is a clique in $G$ . In $1982$ , Skrien posed the problem of characterizing the class of $1$ -perfectly orientable graphs. This graph class forms a common generalization of the classes of chordal and circular arc graphs; however, while polynomially recognizable via a reduction to $2$ -SAT, no structural characterization of this intriguing class of graphs is known. Based on a reduction of the study of $1$ -perfectly orientable graphs to the biconnected case, we characterize, both in terms of forbidden induced minors and in terms of composition theorems, the classes of $1$ -perfectly orientable $K_4$ -minor-free graphs and of $1$ -perfectly orientable outerplanar graphs. As part of our approach, we introduce a class of graphs defined similarly as the class of $2$ -trees and relate the classes of graphs under consideration to two other graph classes closed under induced minors studied in the literature: cyclically orientable graphs and graphs of separability at most~ $2$ .

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 total domination in the Cartesian product of graphs

Ho proved in [A note on the total domination number, Util.Math. 77 (2008) 97--100] that the total domination number of the Cartesian product of any two graphs with no isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and $K_2$ or $C_n$ , Util. Math. 83 (2010) 313--322] by characterizing the pairs of graphs $G$ and $H$ for which $γ_t(G\Box H)=\frac{1}{2}γ_t(G) γ_t(H)\,$ , whenever $γ_t(H)=2$ . In addition, we present an infinite family of graphs $G_n$ with $γ_t(G_n)=2n$ , which asymptotically approximate the equality in $γ_t(G_n\Box G_n)\ge \frac{1}{2}γ_t(G_n)^2$ .

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.

preprint2016arXiv

Total dominating sequences in trees, split graphs, and under modular decomposition

A sequence of vertices in a graph $G$ with no isolated vertices is called a total dominating sequence if every vertex in the sequence totally dominates at least one vertex that was not totally dominated by preceding vertices in the sequence, and, at the end all vertices of $G$ are totally dominated (by definition a vertex totally dominates its neighbors). The maximum length of a total dominating sequence is called the Grundy total domination number, $γ_{\rm gr}^t(G)$ , of $G$ , as introduced in [B. Brešar, M.A. Henning, and D. F. Rall, Total dominating sequences in graphs, Discrete Math. 339 (2016), 1165--1676]. In this paper we continue the investigation of this concept, mainly from the algorithmic point of view. While it was known that the decision version of the problem is NP-complete in bipartite graphs, we show that this is also true if we restrict to split graphs. A linear time algorithm for determining the Grundy total domination number of an arbitrary tree $T$ is presented, based on the formula $γ_{\rm gr}^t(T)=2τ(T)$ , where $τ(T)$ is the vertex cover number of $T$ . A similar efficient algorithm is presented for bipartite distance-hereditary graphs. Using the modular decomposition of a graph, we present a frame for obtaining polynomial algorithms for this problem in classes of graphs having relatively simple modular subgraphs. In particular, a linear algorithm for determining the Grundy total domination number of $P_4$ -tidy graphs is presented. In addition, we prove a realization result by exhibiting a family of graphs $G_k$ such that $γ_{\rm gr}^t(G_k)=k$ , for any $k\in{\mathbb{Z}^+}\setminus\{1,3\}$ , and showing that there are no graphs $G$ with $γ_{\rm gr}^t(G)\in \{1,3\}$ . We also present such a family, which has minimum possible order and size among all graphs with Grundy total domination number equal to $k$ .

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.

preprint2010arXiv

Minimum k-path vertex cover

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψ_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining ψ_k(G) is NP-hard for each k \geq 2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψ_k(G) and provide several estimations and exact values of ψ_k(G). We also prove that ψ_3(G) \leq (2n + m)/6, for every graph G with n vertices and m edges.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Boštjan Brešar

Research overview

Is this your work?

13 publications

The geodesic-transversal problem

$S$ -packing colorings of distance graphs $G(\mathbb{Z},\{2,t\})$

Domination in digraphs and their products

Packing colorings of subcubic outerplanar graphs

$1$ -perfectly orientable $K_4$ -minor-free and outerplanar graphs

Complexity of the Game Domination Problem

Dominating sequences in grid-like and toroidal graphs

On total domination in the Cartesian product of graphs

Packing chromatic number under local changes in a graph

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

Total dominating sequences in trees, split graphs, and under modular decomposition

Domination game: effect of edge- and vertex-removal

Minimum k-path vertex cover

See the researcher in context

Building this map preview

Boštjan Brešar

Research overview

Is this your work?

13 publications

The geodesic-transversal problem

SSS-packing colorings of distance graphs G(Z,{2,t})G(\mathbb{Z},\{2,t\})G(Z,{2,t})

Domination in digraphs and their products

Packing colorings of subcubic outerplanar graphs

111-perfectly orientable K4K_4K4​-minor-free and outerplanar graphs

Complexity of the Game Domination Problem

Dominating sequences in grid-like and toroidal graphs

On total domination in the Cartesian product of 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

Total dominating sequences in trees, split graphs, and under modular decomposition

Domination game: effect of edge- and vertex-removal

Minimum k-path vertex cover

See the researcher in context

Building this map preview

$S$ -packing colorings of distance graphs $G(\mathbb{Z},\{2,t\})$

$1$ -perfectly orientable $K_4$ -minor-free and outerplanar graphs

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