Tightness of Paired and Upper Domination Inequalities for Direct Product Graphs

preprint2020arXivOpen access

Abstract

A set DD of vertices in a graph GG is called dominating if every vertex of GG is either in DD or adjacent to a vertex of DD. The paired domination number γpr(G)γ_{\mathrm{pr}}(G) of GG is the minimum size of a dominating set whose induced subgraph admits a perfect matching, and the upper domination number Γ(G)Γ(G) is the maximum size of a minimal dominating set. In this paper, we investigate the sharpness of two multiplicative inequalities for these domination parameters, where the graph product is the direct product ×\times. We show that for every positive constant cc, there exist graphs GG and HH of arbitrarily large diameter such that γpr(G×H)≤cγpr(G)γpr(H)γ_{\mathrm{pr}}(G \times H) \leq cγ_{\mathrm{pr}}(G)γ_{\mathrm{pr}}(H), thus answering a question of Rall as well as two questions of Paulraja and Sampath Kumar. We then study when this inequality holds with c=12c = \frac{1}{2}, in particular proving that it holds whenever GG and HH are trees. Finally, we demonstrate that the inequality Γ(G×H)≥Γ(G)Γ(H)Γ(G \times H) \geq Γ(G) Γ(H), due to Brešar, Klavžar, and Rall, is tight.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.