Double Domination in the Cartesian and Tensor Products of Graphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A subset S of V(G), where G is a graph without isolated vertices, is a double dominating set of G if for each x ∈ V(G), | NG[x]∩S|≥2. This paper, shows that any positive integers a, b and n with 2 ≤ a< b, b ≥ 2a and n ≥ b+2a-2, can be realized as domination number, double domination number and order, respectively. It also characterize the double dominating sets in the Cartesian and tensor products of two graphs and determine sharp bounds for the double domination numbers of these graphs. In particular, it show that if G and H are any connected non-trivial graphs of orders n and m respectively, then γ×2(G□H) ≤ min{mγ2(G),nγ2(H)}, where γ2, is the 2-domination parameter.
Abstract
A subset S of V(G), where G is a graph without isolated vertices, is a double dominating set of G if for each x ∈ V(G), | NG[x]∩S|≥2. This paper, shows that any positive integers a, b and n with 2 ≤ a< b, b ≥ 2a and n ≥ b+2a-2, can be realized as domination number, double domination number and order, respectively. It also characterize the double dominating sets in the Cartesian and tensor products of two graphs and determine sharp bounds for the double domination numbers of these graphs. In particular, it show that if G and H are any connected non-trivial graphs of orders n and m respectively, then γ×2(G□H) ≤ min{mγ2(G),nγ2(H)}, where γ2, is the 2-domination parameter.
참고문헌 (6)
- M. Atapour., "Characterization of double domination subdivision number of trees", Discrete Applied Mathematics, 155, pp.1700~1707 (2007)
- M. Blidia., "Characterization of trees with equal paired and double domination numbers", Discrete Mathematics, 306, pp.1840~1845 (2006)
- A. Cuivillas., "Double domination in graphs under some binary operations", Applied Mathematical Sciences, 8, pp.2015~2024 (2014)
- F. Harary., "Double domination in graphs", Arts Combin, 55, pp.201~213 (2000)
- F. Harary., "Norhdhaus-Gaddum inequalities for domination in graphs", Discrete Mathematics, 155, pp.99~105 (1996)
- S. Khelifi., "Double domination edge removal critical graphs", Australasian Journal of Combinatorics, 48, pp.285~299 (2010)