9346

8628

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

علوم رياضي- رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1393

[هفت]،76ص.: مصور،جدول

ص.ع.به فارسي و انگليسي

بهناز عمومي

محسن جان نثاري

16/9/93

غلامرضا اميدي، محمدرضا عبودي

رياضي

ID8628

Resolving sets for Johnson and Kneser graphs Mohammad Bagher Banavand mb banavand@math iut ac ir September 20 2014 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Behnaz Omoomi bomoomi@cc iut ac ir Advisor Dr Mohsen Jannesari mjannesari@shahreza ac ir 2010 MSC 05C12 05B05 05E18 05C 90 Keywords Johnson graph Kneser graph Resolving set Metric basis Metric dimension AbstractLet G V G E G be a nite simple and connected graph As usual the distancebetween two vertices u and v is denoted by dG u v or simply d u v if the graph G isclear A vertex x V G is said to resolve a pair u v V G if dG u x dG v x So a set of vertices S in a graph G is a resolving set for G if for any two vertices u and v there exists x S such that d u x d v x In other words a resolving set for G is a setof vertices S s1 sk such that for each arbitrarily vertex such v the ordered list ofdistances r v S d v s1 d v sk uniquely determines v where r v S is the metricrepresentation of v with respect to S That is S is a resolving set for G if for any twodistinct vertices u and v r u S r v S The metric dimension of G denoted by G isthe smallest size of all resolving sets of G The metric dimension is a well known parameter in graph theory It was rst introduced inthe 1975s In 37 Slater introduced the idea of a resolving set and used the terminologylocating set and the location number for what we call a resolving set and the metric dimension

بهناز عمومي

محسن جان نثاري

غلامرضا اميدي، محمدرضا عبودي