Source author record

Magda Dettlaff

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

6works

1topics

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.

preprint2020arXiv

Critical graphs upon multiple edge subdivision

A subset $D$ of $V$ is \emph{dominating} in $G$ if every vertex of $V-D$ has at least one neighbour in $D;$ let $γ(G)$ be the minimum cardinality among all dominating sets in $G.$ A graph $G$ is $γ$ - $q$ -{\it critical} if the smallest subset of edges whose subdivision necessarily increases $γ(G)$ has cardinality $q.$ In this paper we consider mainly $γ$ - $q$ -critical trees and give some general properties of $gamma$ - $q$ -critical graphs. In particular, we show that if $T$ is a $γ$ - $q$ -critical tree, then $1 \leq q \leq n(T)-1$ and we characterize extremal trees when $q=n(T)-1.$ Since a subdivision number {of a tree $T$ } ${\rm sd}(T)$ is always $1,2$ or $3,$ we also characterize $γ$ -2-critical trees $T$ with ${\rm sd}(T)=2$ and $γ$ -3-critical trees $T$ with ${\rm sd}(T)=3.$

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.

preprint2014arXiv

Bondage number of grid graphs

The bondage number $b(G)$ of a nonempty graph $G$ is the cardinality of a smallest set of edges whose removal from $G$ results in a graph with domination number greater than the domination number of $G$ . Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

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.

preprint2013arXiv

Total domination multisubdivision number of a graph

The domination multisubdivision number of a nonempty graph $G$ was defined as the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the domination number of $G$ . Similarly we define the total domination multisubdivision number msd $_{γ_t}(G)$ of a graph $G$ and we show that for any connected graph $G$ of order at least two, msd $_{γ_t}(G)\leq 3.$ We show that for trees the total domination multisubdivision number is equal to the known total domination subdivision number. We also determine the total domination multisubdivision number for some classes of graphs and characterize trees $T$ with msd $_{γ_t}(T)=1$ .

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.