Source author record

Mateusz Miotk

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

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.

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.