Domination parameters of strong product of directed paths
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In a digraph D = (V (D),A(D)), a vertex u dominates a vertex v if u = v or uv ∈ A(D). A set S ⊆ V (D) is a dominating set of D if any vertex of V (D) is dominated by at least one vertex of S. The domination number of D, denoted by γ(D), is the minimum cardinality of a dominating set of D. A two-valued function f : V (D) → {−1, 1} defined on the vertices of D is called a signed dominating function if f(N−[v]) ≥ 1 for every v in D. The weight of a signed dominating function is f(V (D)) = ∑v∈V (D) f(v). The minimum weight of a signed dominating function of D is the signed domination number γs(D) of D. Let Pm ⊠ Pn be the strong product of directed paths Pm and Pn. In this paper, we determine the exact values of γ(Pm ⊠ Pn) and γs(Pm ⊠ Pn) for any m and n, respectively.
Abstract
In a digraph D = (V (D),A(D)), a vertex u dominates a vertex v if u = v or uv ∈ A(D). A set S ⊆ V (D) is a dominating set of D if any vertex of V (D) is dominated by at least one vertex of S. The domination number of D, denoted by γ(D), is the minimum cardinality of a dominating set of D. A two-valued function f : V (D) → {−1, 1} defined on the vertices of D is called a signed dominating function if f(N−[v]) ≥ 1 for every v in D. The weight of a signed dominating function is f(V (D)) = ∑v∈V (D) f(v). The minimum weight of a signed dominating function of D is the signed domination number γs(D) of D. Let Pm ⊠ Pn be the strong product of directed paths Pm and Pn. In this paper, we determine the exact values of γ(Pm ⊠ Pn) and γs(Pm ⊠ Pn) for any m and n, respectively.
참고문헌 (24)
- A. Bhattacharya, "Domination in digraphs and variants of domination in graphs", J. Comb. Inf. Syst. Sci., 30, pp.19~24 (2005)
- G. Chartrand, "On the out-domination and in-domination numbers of a digraph", Discrete Math., 197, pp.198 (1999), 179~183
- G. Chartrand, "Graphs and digraphs" (2005), Chapman and Hall
- W. Chen, "Lower bounds on several versions of signed domination number", Discrete Math., 308, pp.1837~1846 (2008)
- J.E. Dunbar, "Signed domination in graphs, Graph Theory, Combinatorics, and Applications", pp.311~322 (1995), John Wiley Sons, Inc
- O. Favaron, "Signed domination in regular graphs", Discrete Math., 158, pp.287~293 (1996)
- T.W. Haynes, "Foundamentals of domination in graphs" (1998), Marcel Dekker
- R. Hammack, "Handbook of Product Graphs" (2011), CRC Press
- N. Kumar, "Capacity and interference aware link scheduling with channel assignment in wireless mesh networks", Journal of Net-work and Computer Applications, 34, pp.30~38 (2011)
- V. Koltun, "Approximately dominating representatives", ICDT ’05: Proceedings of international conference on data theory (2005)
- H. Karami, "Lower bounds on the signed domination numbers of directed graphs", Discrete Math., 309, pp.2567~2570 (2009)
- C. Lee, "Domination in digraphs", J. Korean Math. Soc., 35, pp.843~853 (1998)
- J. Liu, "The domination number of Carte-sian products of directed cycles", Inform. Process. Lett., 110, pp.171~173 (2010)
- J. Liu, "On domination number of Cartesian product of directed paths", J. Combin. Optim, 22, pp.651~662 (2011)
- J. Matouek, "On the signed domination in graphs", Combinatorica, 20, pp.103~108 (2000)
- M. Mollard, "On domination of Cartesian product of directed cycles", Discuss. Math. Graph Theory, 33 (2013)
- M. Mollard, "The domination number of Cartesian product of two directed paths", J. Combin. Optim., 27, pp.144~151 (2014)
- C.Y. Pang, "Dominating sets in directed graphs", Information Sciences, 180, pp.3647~3652 (2010)
- R.S. Shaheen, "Domination number of toroidal grid digraphs", Utilitas Math., 78, pp.175~184 (2009)
- 손무영, "Lower bounds of signed domination number of a graph", 대한수학회보, 41(1), pp.181~188 (2004), 대한수학회
- L. Volkmann, "Signed domination and signed domatic numbers of digraphs", Dis-cuss. Math. Graph Theory, 31, pp.415~421 (2011)
- J. Wu, "Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links", IEEE Trans. Parallel Distrib. Syst., 13, pp.866~881 (2002)
- B. Zelinka, "Signed domination numbers of directed graphs", Czechoslovak Math-ematical Journal, 55, pp.479~482 (2005)
- X.D. Zhang, "Domination number of Cartesian products of directed cycles", Inform. Process. Lett., 111, pp.36~39 (2010)