چکیده: فرض کنیم G یک گراف ساده با مجموعه رأس‌های V باشد. برای هر v∈V و هر عدد r≥1، گوی به‌مرکز v و به‌شعاع r را با نماد (B_(G,r) (v نشان می‌دهیم. مجموعه C⊆V یک کد r-شناسایی در گراف G می‌نامیم هرگاه مجموعه‌های B_(G,r) (v)∩C، برای هر v∈V، همگی غیرتهی و متمایز باشند. گراف G که دارای کد r-شناسایی باشد را یک گراف r-قابل شناسایی می‌نامند و در این حالت اندازه‌ی کوچکترین کد r-شناسایی در گراف G را با (id(G نشان می‌دهیم. در این پایان‌نامه اندازه‌ی کدهای r-شناسایی که دارای ویژگی (C|=id(G| می‌باشند، و سعی می‌کنیم گراف‌هایی بسازیم که دارای تعداد زیاد از این چنین کدهایی باشند. برای گراف G، فرض کنیم (idor(G کوچکترین اندازه‌ی (id(D روی تمام گراف‌های جهت‌دار D حاصل از جهت‌دهی‌های مختلف ممکن از گراف G باشد. در این پایان‌نامه، برخی کران‌های بالا و کران‌های پایین را برای پارامتر (idor(G به‌دست می‌آوریم. نشان می‌دهیم که برای هر گراف G داریم (indor(G)<= (3/2)id(G . هم‌چنین نشان می‌دهیم که مسأله محاسبه‌ی (idor(G، یک مسأله NP-سخت بوده، در حالی که مسأله‌ی تصمیم این‌که آیا نامساوی idor(G)≤|V(G)|-k برای هر عدد ثابت k ، برقرار می‌باشد یا نه، یک مسأله حل‌پذیر در زمان چندجمله‌ای می‌باشد