An Improved Bound for Upper Domination of Cartesian Products of Graphs

2017/03/17 by Yu-Yen Chien, Chien, Yu-Yen
Computer Science · #05C69 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1703.05861

openalex publication_date 2017/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we prove a problem proposed by Brešar: for any graphs G and H, Γ(G\square H)≥Γ(G)Γ(H)+ min\|V(G)|-Γ(G),|V(H)|-Γ(H)\, where Γ(G) denotes the upper domination number of G.

Related

• On total domination in the Cartesian product of graphs
• A Note on Total and Paired Domination of Cartesian Product Graphs
• An improved bound in Vizing's conjecture
• On the domination number of the cartesian product of the path graph and any pair of graphs
• A Note on Integer Domination of Cartesian Product Graphs