BSBabak Samadi

Babak Samadi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Babak Samadi has a total of 20 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Limited packings: related vertex partitions and duality issues

    by Azam Sadat Ahmadi, Nasrin Soltankhah, Babak Samadi

    A $k$-limited packing partition ($k$LP partition) of a graph $G$ is a partition of $V(G)$ into $k$-limited packing sets. We consider the $k$LP partitions with minimum cardinality (with emphasis on $k=2$). The minimum cardinality is called $k$LP partition number of $G$ and denoted by $χ_{\times k}(G)$. This problem is the dual problem of $k$-tuple domatic partitioning as well as a generalization of the well-studied $2$-distance coloring problem in graphs. We give the exact value of $χ_{\times2}$ for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in $1998$. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between $2$TLP number and $2$LP number with emphasis on trees.

  • Open Access

    Further results on outer independent 2-rainbow dominating functions of graphs

    by Babak Samadi, Nasrin Soltankhah

    Let G = (V(G), E(G)) be a graph. A function f : V(G) → ℙ({1, 2}) is a 2-rainbow dominating function if for every vertex v with f(v) = ∅, f(N(v)) = {1, 2}. An outer-independent 2-rainbow dominating function (OI2RD function) of G is a 2-rainbow dominating function f for which the set of all v 2208 V(G) with f(v) = ∅ is independent. The outer independent 2-rainbow domination number (OI2RD number) γoir2(G) is the minimum weight of an OI2RD function of G. In this paper, we first prove that n/2 is a lower bound on the OI2RD number of a connected claw-free graph of order n and characterize all such graphs for which the equality holds, solving an open problem given in an earlier paper. In addition, a study of this parameter for some graph products is carried out. In particular, we give a closed (resp. an exact) formula for the OI2RD number of rooted (resp. corona) product graphs and prove upper bounds on this parameter for the Cartesian product and direct product of two graphs.

  • Open Access

    Injective coloring of product graphs

    by Babak Samadi, Nasrin Soltankhah, Ismael G. Yero

    The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs.

  • Open Access

    Further results on outer independent $2$-rainbow dominating functions of graphs

    by Babak Samadi, Nasrin Soltankhah

    Let $G=(V(G),E(G))$ be a graph. A function $f:V(G)\rightarrow \mathbb{P}(\{1,2\})$ is a $2$-rainbow dominating function if for every vertex $v$ with $f(v)=\emptyset$, $f\big{(}N(v)\big{)}=\{1,2\}$. An outer-independent $2$-rainbow dominating function (OI$2$RD function) of $G$ is a $2$-rainbow dominating function $f$ for which the set of all $v\in V(G)$ with $f(v)=\emptyset$ is independent. The outer independent $2$-rainbow domination number (OI$2$RD number) $\gamma_{oir2}(G)$ is the minimum weight of an OI$2$RD function of $G$. In this paper, we first prove that $n/2$ is a lower bound on the OI$2$RD number of a connected claw-free graph of order $n$ and characterize all such graphs for which the equality holds, solving an open problem given in an earlier paper. In addition, a study of this parameter for some graph products is carried out. In particular, we give a closed (resp. an exact) formula for the OI$2$RD number of rooted (resp. corona) product graphs and prove upper bounds on this parameter for the Cartesian product and direct product of two graphs.

  • Open Access

    Restrained condition on double Roman dominating functions

    by B. Samadi, N. Soltankhah, H. Abdollahzadeh Ahangar, M. Chellali, D.A. Mojdeh, S.M. Sheikholeslami, J.C. Valenzuela-Tripodoro


  • Open Access

    Restrained condition on double Roman dominating functions

    by Babak Samadi, Nasrin Soltankhah, H. Abdollahzadeh Ahangar, M. Chellali, Doost Ali Mojdeh, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro

    We continue the study of restrained double Roman domination in graphs. For a graph $G=\big{(}V(G),E(G)\big{)}$, a double Roman dominating function $f$ is called a restrained double Roman dominating function (RDRD function) if the subgraph induced by $\{v\in V(G)\mid f(v)=0\}$ has no isolated vertices. The restrained double Roman domination number (RDRD number) $\gamma_{rdR}(G)$ is the minimum weight $\sum_{v\in V(G)}f(v)$ taken over all RDRD functions of $G$. We first prove that the problem of computing $\gamma_{rdR}$ is NP-hard even for planar graphs, but it is solvable in linear time when restricted to bounded clique-width graphs such as trees, cographs and distance-hereditary graphs. Relationships between $\gamma_{rdR}$ and some well-known parameters such as restrained domination number $\gamma_{r}$, domination number $\gamma$ and restrained Roman domination number $\gamma_{rR}$ are investigated in this paper by bounding $\gamma_{rdR}$ from below and above involving $\gamma_{r}$, $\gamma$ and $\gamma_{rR}$ for general graphs, respectively. We prove that $\gamma_{rdR}(T)\geq n+2$ for any tree $T\neq K_{1,n-1}$ of order $n\geq2$ and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper.

  • Open Access

    On the Packing Partitioning Problem on Directed Graphs

    by Babak Samadi, Ismael G. Yero

    This work is aimed to continue studying the packing sets of digraphs via the perspective of partitioning the vertex set of a digraph into packing sets (which can be interpreted as a type of vertex coloring of digraphs) and focused on finding the minimum cardinality among all packing partitions for a given digraph D, called the packing partition number of D. Some lower and upper bounds on this parameter are proven, and their exact values for directed trees are given in this paper. In the case of directed trees, the proof results in a polynomial-time algorithm for finding a packing partition of minimum cardinality. We also consider this parameter in digraph products. In particular, a complete solution to this case is presented when dealing with the rooted products.