Source author record

Simone Dantas

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

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the Graceful Game

A graceful labeling of a graph $G$ with $m$ edges consists of labeling the vertices of $G$ with distinct integers from $0$ to $m$ such that, when each edge is assigned as induced label the absolute difference of the labels of its endpoints, all induced edge labels are distinct. Rosa established two well known conjectures: all trees are graceful (1966) and all triangular cacti are graceful (1988). In order to contribute to both conjectures we study graceful labelings in the context of graph games. The Graceful game was introduced by Tuza in 2017 as a two-players game on a connected graph in which the players Alice and Bob take turns labeling the vertices with distinct integers from 0 to $m$ . Alice's goal is to gracefully label the graph as Bob's goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in complete graphs, paths, cycles, complete bipartite graphs, caterpillars, prisms, wheels, helms, webs, gear graphs, hypercubes and some powers of paths.

preprint2015arXiv

Averaging $2$ -Rainbow Domination and Roman Domination

For a graph $G$ , let $γ_{r2}(G)$ and $γ_R(G)$ denote the $2$ -rainbow domination number and the Roman domination number, respectively. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) proved $γ_{r2}(G)+γ_R(G)\leq \frac{6}{4}n(G)$ for a connected graph $G$ of order $n(G)$ at least $3$ . Furthermore, they conjectured $γ_{r2}(G)+γ_R(G)\leq \frac{4}{3}n(G)$ for a connected graph $G$ of minimum degree at least $2$ that is distinct from $C_5$ . We characterize all extremal graphs for their inequality and prove their conjecture.

preprint2015arXiv

Dominating Sets inducing Large Components in Maximal Outerplanar Graphs

For a maximal outerplanar graph $G$ of order $n$ at least $3$ , Matheson and Tarjan showed that $G$ has domination number at most $n/3$ . Similarly, for a maximal outerplanar graph $G$ of order $n$ at least $5$ , Dorfling, Hattingh, and Jonck showed, by a completely different approach, that $G$ has total domination number at most $2n/5$ unless $G$ is isomorphic to one of two exceptional graphs of order $12$ . We present a unified proof of a common generalization of these two results. For every positive integer $k$ , we specify a set ${\cal H}_k$ of graphs of order at least $4k+4$ and at most $4k^2-2k$ such that every maximal outerplanar graph $G$ of order $n$ at least $2k+1$ that does not belong to ${\cal H}_k$ has a dominating set $D$ of order at most $\lfloor\frac{kn}{2k+1}\rfloor$ such that every component of the subgraph $G[D]$ of $G$ induced by $D$ has order at least $k$ .

preprint2015arXiv

Relating $2$ -Rainbow Domination to Roman domination

For a graph $G$ , let $γ_R(G)$ and $γ_{r2}(G)$ denote the Roman domination number of $G$ and the $2$ -rainbow domination number of $G$ , respectively. It is known that $γ_{r2}(G)\leq γ_R(G)\leq \frac{3}{2}γ_{r2}(G)$ . Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) present some kind of characterization of the graphs $G$ for which $γ_R(G)-γ_{r2}(G)=k$ for some integer $k$ . Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer $k$ , the recognition of the connected $K_4$ -free graphs $G$ with $γ_R(G)-γ_{r2}(G)=k$ is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs $G$ such that $γ_{r2}(H)=γ_R(H)$ for every induced subgraph $H$ of $G$ , and collect several properties of the graphs $G$ with $γ_R(G)=\frac{3}{2}γ_{r2}(G)$ .

preprint2015arXiv

Relating $2$ -rainbow domination to weak Roman domination

Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27-32) we prove $γ_{r2}(G)\leq 2γ_r(G)$ for every graph $G$ , where $γ_{r2}(G)$ and $γ_r(G)$ denote the $2$ -rainbow domination number and the weak Roman domination number of $G$ , respectively. We characterize the extremal graphs for this inequality that are $\{ K_4,K_4-e\}$ -free, and show that the recognition of the $K_5$ -free extremal graphs is NP-hard.

preprint2015arXiv

Strong Equality of Roman and Weak Roman Domination in Trees

We provide a constructive characterization of the trees for which the Roman domination number strongly equals the weak Roman domination number, that is, for which every weak Roman dominating function of minimum weight is a Roman dominating function. Our characterization is based on five simple extension operations, and reveals several structural properties of these trees.

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.

Simone Dantas

Research overview

Is this your work?

6 publications

On the Graceful Game

Averaging $2$ -Rainbow Domination and Roman Domination

Dominating Sets inducing Large Components in Maximal Outerplanar Graphs

Relating $2$ -Rainbow Domination to Roman domination

Relating $2$ -rainbow domination to weak Roman domination

Strong Equality of Roman and Weak Roman Domination in Trees

See the researcher in context

Building this map preview

Simone Dantas

Research overview

Is this your work?

6 publications

On the Graceful Game

Averaging 222-Rainbow Domination and Roman Domination

Dominating Sets inducing Large Components in Maximal Outerplanar Graphs

Relating 222-Rainbow Domination to Roman domination

Relating 222-rainbow domination to weak Roman domination

Strong Equality of Roman and Weak Roman Domination in Trees

See the researcher in context

Building this map preview

Averaging $2$ -Rainbow Domination and Roman Domination

Relating $2$ -Rainbow Domination to Roman domination

Relating $2$ -rainbow domination to weak Roman domination