On the complexity of locating-total domination in bipartite graphs

سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 373

فایل این مقاله در 5 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

DSCONF06_082

تاریخ نمایه سازی: 23 شهریور 1398

چکیده مقاله:

A total dominating set of a graph G = (V, E) with no isolated vertex is a set D ⊆ V (G) such that every vertex is adjacent to a vertex in D. A total dominating set D of G is a locating-total dominating set if for every pair of distinct vertices u and v in V − D, N(u) ∩ D ≠ N(v) ∩ D. Let γtL(G) be the minimum cardinality of a locating-total dominating set of G. We show that the decision problem for locating-total domination number is NP-complete for bipartite graphs. We thus answer some open problems in [M. Miller, R. R. (2017). A not on locating-total domination in graphs. Discussiones Math. Graph Theory, 383-392].

نویسندگان

N. A. Doostimotlagh

Supreme National Defense University