Source author record

Jerzy Topp

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Common domination perfect graphs

A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex that does not belong to $S$ is adjacent to a vertex in $S$ . The domination number $γ(G)$ of $G$ is the minimum cardinality of a dominating set of $G$ . The common independence number $α_c(G)$ of $G$ is the greatest integer $r$ such that every vertex of $G$ belongs to some independent set of cardinality at least~ $r$ . The common independence number is squeezed between the independent domination number $i(G)$ and the independence number $α(G)$ of $G$ , that is, $γ(G) \le i(G) \le α_c(G) \le α(G)$ . A graph $G$ is domination perfect if $γ(H) = i(H)$ for every induced subgraph $H$ of $G$ . We define a graph $G$ as common domination perfect if $γ(H) = α_c(H)$ for every induced subgraph $H$ of $G$ . We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs.

preprint2021arXiv

Minimal graphs with disjoint dominating and total dominating sets

A graph $G$ is a DTDP-graph if it has a pair $(D,T)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $T$ is a total dominating set of $G$ . Such graphs were studied in a number of research papers. In this paper we study further properties of DTDP-graphs and, in particular, we characterize minimal DTDP-gaphs without loops.

preprint2019arXiv

Minimal graphs with disjoint dominating and paired-dominating sets

A subset $D\subseteq V_G$ is a dominating set of $G$ if every vertex in $V_G-D$ has a~neighbor in $D$ , while $D$ is a paired-dominating set of $G$ if $D$ is a~dominating set and the subgraph induced by $D$ contains a perfect matching. A graph $G$ is a $D\!P\!D\!P$ -graph if it has a pair $(D,P)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $P$ is a paired-dominating set of $G$ . The study of the $D\!P\!D\!P$ -graphs was initiated by Southey and Henning (Cent. Eur. J. Math. 8 (2010) 459--467; J. Comb. Optim. 22 (2011) 217--234). In this paper, we provide conditions which ensure that a graph is a $D\!P\!D\!P$ -graph. In particular, we characterize the minimal $D\!P\!D\!P$ -graphs.

preprint2018arXiv

Graphs with equal domination and covering numbers

A dominating set of a graph $G$ is a set $D\subseteq V_G$ such that every vertex in $V_G-D$ is adjacent to at least one vertex in $D$ , and the domination number $γ(G)$ of $G$ is the minimum cardinality of a dominating set of $G$ . A set $C\subseteq V_G$ is a covering set of $G$ if every edge of $G$ has at least one vertex in $C$ . The covering number $β(G)$ of $G$ is the minimum cardinality of a covering set of $G$ . The set of connected graphs $G$ for which $γ(G)=β(G)$ is denoted by ${\cal C}_{γ=β}$ , while ${\cal B}$ denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to ${\cal C}_{γ=β}$ and ${\cal B}$ . Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to ${\cal B}$ , and, as a side result, we conclude that the algorithm of Arumugam et al. [2] allows to recognize all the graphs belonging to the set ${\cal C}_{γ=β}$ in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that this problem can be solved in $O(n \log n + m)$ time, where $n$ is the number of line segments of the input grid and $m$ is the number of its intersection points.

preprint2017arXiv

On accurate domination in graphs

A dominating set of a graph $G$ is a subset $D \subseteq V_G$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$ . The cardinality of a smallest dominating set of $G$ , denoted by $γ(G)$ , is the domination number of $G$ . The accurate domination number of $G$ , denoted by $γ_{\rm a}(G)$ , is the cardinality of a smallest set $D$ that is a dominating set of $G$ and no $|D|$ -element subset of $V_G \setminus D$ is a dominating set of $G$ . We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees $G$ for which $γ_{\rm a}(G) = γ(G)$ are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

preprint2016arXiv

Coronas and domination subdivision number of a graph

In this paper, for a graph G and a family of partitions P of vertex neighborhoods of G, we define the general corona G \circ P of G. Among several properties of this new operation, we focus on application general coronas to a new kind of characterization of trees with the domination subdivision number equal to 3.

preprint2015arXiv

Hangable Graphs

Let $G=(V_G,E_G)$ be a connected graph. The distance $d_G(u,v)$ between vertices $u$ and $v$ in $G$ is the length of a shortest $u-v$ path in $G$ . The eccentricity of a vertex $v$ in $G$ is the integer $e_G(v)= \max\{ d_G(v,u) \colon u\in V_G\}$ . The diameter of $G$ is the integer $d(G)= \max\{e_G(v)\colon v\in V_G\}$ . The periphery of a~vertex $v$ of $G$ is the set $P_G(v)= \{u\in V_G\colon d_G(v,u)= e_G(v)\}$ , while the periphery of $G$ is the set $P(G)= \{v\in V_G\colon e_G(v)=d(G)\}$ . We say that graph $G$ is hangable if $P_G(v)\subequal P(G)$ for every vertex $v$ of $G$ . In this paper we prove that every block graph is hangable and discuss the hangability of products of graphs.

preprint2013arXiv

Domination subdivision and domination multisubdivision numbers of graphs

The \emph{domination subdivision number} sd $(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of $G$ . It has been shown \cite{vel} that sd $(T)\leq 3$ for any tree $T$ . We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the \emph{domination multisubdivision number} of a nonempty graph $G$ as a minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the domination number of $G$ . We show that msd $(G)\leq 3$ for any graph $G$ . The domination subdivision number and the domination multisubdivision numer of a graph are incomparable in general case, but we show that for trees these two parameters are equal. We also determine domination multisubdivision number for some classes of graphs.

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.