Transferable domination number of graphs

Fei Huang Chang, Ma Lian Chia, David Kuo, Wen Deng, Sheng Chyang Liaw, Zhishi Pan

研究成果: 雜誌貢獻期刊論文同行評審

摘要

Let G be a connected graph, and let D(G) be the set of all dominating (multi)sets for G. For D1 and D2 in D(G), we say that D1 is single-step transferable to D2 if there exist u∈D1 and v∈D2, such that uv∈E(G) and D1−{u}=D2−{v}. We write D1⟶∗D2 if D1 can be transferred to D2 through a sequence of single-step transfers. We say that G is k-transferable if D1⟶∗D2 for any D1,D2∈D(G) with |D1|=|D2|=k. The transferable domination number of G is the smallest integer k to guarantee that G is l-transferable for all l≥k. We study the transferable domination number of graphs in this paper. We give upper bounds for the transferable domination number of general graphs and bipartite graphs, and give a lower bound for the transferable domination number of grids. We also determine the transferable domination number of Pm×Pn for the cases that m=2,3, or mn≡0(mod6). Besides these, we give an example to show that the gap between the transferable domination number of a graph G and the smallest number k so that G is k-transferable can be arbitrarily large.

原文???core.languages.en_GB???
頁(從 - 到)135-146
頁數12
期刊Discrete Applied Mathematics
313
DOIs
出版狀態已出版 - 31 5月 2022

指紋

深入研究「Transferable domination number of graphs」主題。共同形成了獨特的指紋。

引用此