2024/04/03 by Sergio Bermudo, Iztok Peterin, Bermudo, Sergio +5 · 1 citation
Computer Science · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #Advanced Algebra and Logic
paper · pdf · doi:10.48550/arxiv.2404.02853
The modular product G\diamond H of graphs G and H is a graph on vertex set V(G)× V(H). Two vertices (g,h) and (g′,h′) of G\diamond H are adjacent if g=g′ and hh′∈ E(H), or gg′∈ E(G) and h=h′, or gg′∈ E(G) and hh′∈ E(H), or (for g≠ g′ and h≠ h′) gg′∉ E(G) and hh′∉ E(H). A set D⊆ V(G) is a dominating set of G if every vertex outside of D contains a neighbor in D. A set D⊆ V(G) is a total dominating set of G if every vertex of G contains a neighbor in D. The domination number γ(G) (resp. total domination number γt(G)) of G is the minimum cardinality of a dominating set (resp. total dominating set) of G. In this work we give several upper and lower bounds for γ(G\diamond H) in terms of γ(G), γ(H), γt(G) and γt(H), where G is the complement graph of G. Further, we fully describe graphs where γ(G\diamond H)=k for k∈\1,2,3\. Several conditions on G and H under which γ(G\diamond H) is at most 4 and 5 are also given. A new type of simultaneous domination γ(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.