Packing and domination parameters in digraphs

DOI10.1016/J.DAM.2019.04.008MaRDI QIDQ2328107zbMATH OpenOpenAlexWikidataFDO

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

Publication date 9 October 2019

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

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

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)

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].

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.

Cites work

• scientific article; zbMATH DE number 1270237 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 3438349 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3226832 (Why is no real title available?)
• scientific article; zbMATH DE number 3341035 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Dominating Set and Converse Dominating Set of a Directed Graph
• Domination, independent domination, and duality in strongly chordal graphs
• Efficient total domination in digraphs
• On a Problem in Graph Theory
• On the domination number of digraphs.
• Relations between packing and covering numbers of a tree
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Total and connected domination in digraphs
• Total domination in digraphs
• Total domination in graphs

Cited in

(11)

• scientific article; zbMATH DE number 6837043 (Why is no real title available?)
• Toward Wojda's conjecture on digraph packing
• A polyhedral view to generalized multiple domination and limited packing
• scientific article; zbMATH DE number 4127236 (Why is no real title available?)
• Orientable domination in product-like graphs
• On the complexity of digraph packings
• scientific article; zbMATH DE number 706830 (Why is no real title available?)
• Domination in digraphs and their direct and Cartesian products
• Total and connected domination in digraphs
• Polynomial reductions between the limited packing and tuple domination problems in graphs
• Packing functions and dominating functions of countable 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)