Packing and domination parameters in digraphs

DOI10.1016/J.DAM.2019.04.008zbMATH Open1423.05074arXiv1805.04038OpenAlexW2801836973WikidataQ127924378 ScholiaQ127924378MaRDI QIDQ2328107FDOQ2328107

B. Samadi, Ismael G. Yero, Doost Ali Mojdeh

Publication date: 9 October 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given a digraph $D=(V,A)$, a set $BsubsetV$ is a packing set in $D$ if there are no arcs joining vertices of $B$ and for any two vertices $x,yinB$ the sets of in-neighbors of $x$ and $y$ are disjoint. The set $S$ is a dominating set (an open dominating set) in $D$ if every vertex not in $S$ (in $V$) has an in-neighbor in $S$. Moreover, a dominating set $S$ is called a total dominating set if the subgraph induced by $S$ has no isolated vertices. The packing sets of maximum cardinality and the (total, open) dominating sets of minimum cardinality in digraphs are studied in this article. We prove that the two optimal sets concerning packing and domination achieve the same value for directed trees, and give some applications of it. We also show analogous equalities for all connected contrafunctional digraphs, and characterize all such digraphs $D$ for which such equalities are satisfied. Moreover, sharp bounds on the maximum and the minimum cardinalities of packing and dominating sets, respectively, are given for digraphs. Finally, we present solutions for two open problems, concerning total and open dominating sets of minimum cardinality, pointed out in [Australas. J. Combin. 39 (2007), 283--292].

Full work available at URL: https://arxiv.org/abs/1805.04038

Recommendations

• Total domination in digraphs
• Total and connected domination in digraphs
• Further results on packing related parameters in graphs
• scientific article; zbMATH DE number 3968612
• On the domination number of digraphs.

zbMATH Keywords

domination numbertotal domination numberpacking numberdirected treecontrafunctional digraphopen domination number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Total Domination in Graphs
• A survey of selected recent results on total domination in graphs
• Domination, independent domination, and duality in strongly chordal graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Title not available (Why is that?)
• On a Problem in Graph Theory
• Efficient total domination in digraphs
• Relations between packing and covering numbers of a tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dominating Set and Converse Dominating Set of a Directed Graph
• Title not available (Why is that?)
• Total and connected domination in digraphs
• Total domination in digraphs
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• Toward Wojda's conjecture on digraph packing
• A polyhedral view to generalized multiple domination and limited packing
• Title not available (Why is that?)
• Orientable domination in product-like graphs
• Domination in digraphs and their direct and Cartesian products
• Title not available (Why is that?)
• On the complexity of digraph packings
• Total and connected domination in digraphs
• Polynomial reductions between the limited packing and tuple domination problems in graphs

This page was built for publication: Packing and domination parameters in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328107)