错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Domination number of modular product graphs

  • Sergio Bermudo,
  • Iztok Peterin,
  • Jelena Sedlar,
  • Riste Škrekovski

摘要

Given two graphs G and H,  their modular product \(G\diamond H\) G H is defined to be the graph with \(V(G\diamond H)=V(G)\times V(H)\) V ( G H ) = V ( G ) × V ( H ) and \(E(G\diamond H)=E(G\Box H)\cup E(G\times H)\cup E(\overline{G}\times \overline{H})\) E ( G H ) = E ( G H ) E ( G × H ) E ( G ¯ × H ¯ ) . A dominating set of G is any set \(D\subseteq V(G)\) D V ( G ) such that every vertex of G not contained in D has a neighbor in D. A total dominating set of G is a dominating set D of G with the additional property that all vertices of D also have a neighbor in D. The domination number \(\gamma (G)\) γ ( G ) (resp. total domination number \(\gamma _{t}(G)\) γ t ( G ) ) of G is the cardinality of a smallest dominating set (resp. total dominating set) of G. In this work we give several upper and lower bounds for \(\gamma (G\diamond H)\) γ ( G H ) in terms of \(\gamma (G),\) γ ( G ) , \(\gamma (H)\) γ ( H ) , \(\gamma _{t}(\overline{G})\) γ t ( G ¯ ) and \(\gamma _{t} (\overline{H})\) γ t ( H ¯ ) , where \(\overline{G}\) G ¯ is the complement graph of G. Further, we fully describe graphs where \(\gamma (G\diamond H)=k\) γ ( G H ) = k for \(k\in \{1,2,3\}\) k { 1 , 2 , 3 } . Several conditions on G and H under which \(\gamma (G\diamond H)\) γ ( G H ) is at most 4 and 5 are also given. A new type of simultaneous domination \(\bar{\gamma }(G)\) γ ¯ ( G ) , defined as the smallest number of vertices that dominates G and totally dominates the complement of G,  emerged as useful and we believe it could be of independent interest. We conclude the paper by proposing few directions for possible further research.