16458

14654

كارشناسي ارشد

رياضي

اصفهان : دانشگاه صنعتي اصفهان

1399

[7]، 92ص.:‌ مصور

بهناز عمومي

غلامرضا اميدي، رامين جوادي

1400/03/04

كتابنامه

رياضي

رياضي

1400/03/04

2689877

Locating Dominating Sets in Graphs Narges Mohajery Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Prof Behnaz Omoomi bomoomi@iut ac ir2000 MSC 05C12 05C69 Keywords Dominating Set Domination Number Location Dominating Set Location Domination Num ber Abstract A subset D of vertices in simple graph G is a dominating set if every vertex outside D has at least oneneighbor in D In addition if both distinct vertices outside D have distinct neighborhoods in D then thisset is called the locating dominating Locating domination number is the size of the smallest locating dominating set which is shown by L G The concept of dominating in graphs is one of the most widelyused concept in real world problems and also one of the most interesting research issues The concept ofthe locating dominating set was first introduced by Slater in 1987 Ore in 1962 stated this classical result that in any graph without an isolated vertex with n vertices there nis a dominating set with a maximum size of Garijo et al 2014 conjecrured that in a graph without 2twins if the number of vertices is large enough then the locating domination number is at most half ofthe neighbor of vertices While there are many graphs without an isolated vertex which their locating domination number is larger than of helf of the number its vertices For example consider the completegraph of Kn we have L Kn n1 Garijo et al 2014 showed the maximum locating domination number among all n vertex twin free graphswith the symbol c and made the following conjecture nConjecture 1 There is a positive number n1 such that for every n n1 c 2Then a stronger conjecture about the locating domination number in various articles is expressed as fol n lows Conjecture 2 If G is a n vertex twin free graph an isolated vertex then L G 2Conjecture 2 is stronger than conjecture 1 because conjecture 2 is only for twin free graphs an isolatedvertices while conjecture 1 is for twin free graphs If conjecture 2 is correct then we have for all large nn vertex twin free graphs c 2In this thesis the concept of locating dominating is studied Regards to the efforts in order to prove Con jecture 1 and 2 we peresent the following known results In 2014 Hernand et al stated that relationship between L G L G 1 is the locating dominatingnumber of the graph G and its complement supplementary graph Garijo et al 2014 used this equation toprove Conjecture 2 for each of the following cases Graphs which their independence number is at least half of the number of vertices n 1 Graphs which at least has clique number of 2

بهناز عمومي

غلامرضا اميدي، رامين جوادي