آمار

تعداد نشریات7
تعداد شماره‌ها399
تعداد مقالات5,389
تعداد مشاهده مقاله5,288,200
تعداد دریافت فایل اصل مقاله4,882,943
Sharifani, Pouyeh, Hooshmandasl, Mohammadreza, Alikhani, Saeid. (1399). A linear-time algorithm to compute total $[1,2]$-domination number of block graphs. نشریه مهندسی عمران امیرکبیر, 1(2), 263-270. doi: 10.22060/ajmc.2020.18444.1035
Pouyeh Sharifani; Mohammadreza Hooshmandasl; Saeid Alikhani. "A linear-time algorithm to compute total $[1,2]$-domination number of block graphs". نشریه مهندسی عمران امیرکبیر, 1, 2, 1399, 263-270. doi: 10.22060/ajmc.2020.18444.1035
Sharifani, Pouyeh, Hooshmandasl, Mohammadreza, Alikhani, Saeid. (1399). 'A linear-time algorithm to compute total $[1,2]$-domination number of block graphs', نشریه مهندسی عمران امیرکبیر, 1(2), pp. 263-270. doi: 10.22060/ajmc.2020.18444.1035
Sharifani, Pouyeh, Hooshmandasl, Mohammadreza, Alikhani, Saeid. A linear-time algorithm to compute total $[1,2]$-domination number of block graphs. نشریه مهندسی عمران امیرکبیر, 1399; 1(2): 263-270. doi: 10.22060/ajmc.2020.18444.1035

A linear-time algorithm to compute total $[1,2]$-domination number of block graphs

AUT Journal of Mathematics and Computing
مقاله 12، دوره 1، شماره 2، آذر 2020، صفحه 263-270    اصل مقاله (431.19 K)
نوع مقاله: Original Article
شناسه دیجیتال (DOI): 10.22060/ajmc.2020.18444.1035
نویسندگان
Pouyeh Sharifani1، 2؛ Mohammadreza Hooshmandasl* 3، 2؛ Saeid Alikhani4
1Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
2Department of Computer Science, Yazd University, Yazd, Iran
3Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran
4Department of Mathematics, Yazd University, Yazd, Iran
چکیده
Let $G=(V, E)$ be a simple graph without isolated vertices. A set $D\subseteq V$ is a total $[1,2]$-dominating set if for every vertex $v\in V , 1\leq |N(v)\cap D|\leq 2$. The total $[1,2]$-domination problem is to determine the total $[1,2]$-domination number $\gamma_{t[1,2]}(G)$, which is the minimum cardinality of a total $[1,2]$-dominating set for a graph $G$. In this paper, we present a linear-time algorithm to compute $\gamma_{t[1,2]}(G)$, for a block graph $G$.
کلیدواژه‌ها
Total $[1,2]$-set؛ Dominating set؛ Block graph
مراجع
[1] A. V. Aho, J. E. Hopcroft, The design and analysis of computer algorithms, Pearson Education India (1974).

[2] A. Bishnu, K. Dutta, A. Gosh, S. Pual, [1,j]-set problem in graphs, Discrete Mathematics 339 (2016), 2215- 2525.

[3] M. Chellali, O. Favaron, T. W. Haynes, S. T. Hedetniemi, A. McRae, Independent [1, k]-sets in graphs, Australasian Journal of Combinatorics 59, 1 (2014), 144-156.

[4] M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. McRae, [1, 2]-sets in graphs, Discrete Applied Mathematics 161, 18 (2013), 2885-2893.

[5] O. Etesami, N. Ghareghani, M. Habib, M. R. Hooshmandasl, R. Naserasr, P. Sharifani, When an optimal dominating set with given constraints exists, Theoretical Computer Science, 780 (2019), 54-65.

[6] A. K. Goharshady, M. R. Hooshmandasl, M. Alambardar Meybodi, [1, 2]-sets and [1, 2]-total sets in trees with algorithms, Discrete Applied Mathematics, 198 (2016), 136-146.

[7] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, CRC Press, 1998.

[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: advanced topics, Marcel Dekker, 1998.

[9] S. T. Hedetniemi, R. Laskar, Topics on domination, Elsevier, 1991.

[10] D. B. West, Introduction to graph theory, 2ed Edition. Prentice hall Upper Saddle River, 2001.

[11] X. Yang, B. Wu, [1, 2]-domination in graphs, Discrete Applied Mathematics, 175 (2014), 79-86.

آمار
تعداد مشاهده مقاله: 1,328
تعداد دریافت فایل اصل مقاله: 647


سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب