Skip to main content
SUPERVISOR
Behnaz Omoomi,Gholamreza Omidi
بهناز عمومی (استاد مشاور) غلامرضا امیدی اردلی (استاد راهنما)
 
STUDENT
Mohammad Rahbar
محمد رهبر

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1389

TITLE

Some Extensions of Strongly Regular Graphs
Let G be a graph which is neither empty nor complete. Then G is said to be a strongly regular graph (SRG) with parameters (v, k, ? , µ ) if G is a k-regular graph on n vertices in which every pair of adjacent vertices has ? common neighbors and every pair of non-adjacent vertices has µ common neighbors. One of the most important family of regular graphs is the family of strongly regular graphs which has so many beautiful properties. One of these well-known properties is the fact that the eigenvalues of all SRGs depend only the parameters of these graphs. There are many SRGs arising from combinatorial concepts such as orthogonal arrays, Latin squares, conference matrices, designs and geometric graphs. In this thesis, the following generalizations of strongly regular graphs has been studied. A graph G is a Deza graph if it is regular and the number of common neighbors of two distinct vertices takes on one of two values (not necessarily depending on the adjacency of the two vertices). Haemers, Erickson, Fernando, Hard and Hemmeter introduced several ways to construct Deza graphs, and develop some basic theory. They also gave list all diameter two Deza graphs which are not strongly regular and have at most 13 vertices. The Friendship Theorem states that if any two people in a party have exactly one common friend, then there exists a politician who is a friend of everybody. Let ? be any nonnegative integer and µ be any positive integer. Suppose each pair of friends have exactly ? common friends and each pair of strangers have exactly µ common friends in a party. The corresponding graph is a generalization of strongly regular graphs obtained by relaxing the regularity property on vertex degrees. Gera and Shen proved that either everyone has exactly the same number of friends or there exists a politician who is a friend of everybody. A k-regular graph on v vertices is a divisible design graph (DDG for short) with parameters(v,k, ? 1 , ? 2 , m, n) whenever the vertex set can be partitioned into m
یک گراف قویاً منظم با پارامترهای (v, k, ?, µ) که باsrg-(v, k, ?, µ) نمایش داده می‌شود، گرافی k-منظم از مرتبه‌ی v است، به‌طوری‌که هر دو رأس مجاور آن ? همسایه مشترک و هر دو رأس نامجاور آن µ همسایه مشترک دارند. گراف‌های قویاً منظم یکی از مهم‌ترین و جالب‌ترین خانواده از گراف‌های منظم هستند که ارتباط زیادی با دیگر ساختارهای ترکیبیاتی مانند آرایه‌های متعامد، مربع‌های لاتین و طرح‌ها دارند به‌طوری‌که بسیاری از گراف‌های قویاً منظم را می‌توان از این ساختارها به‌دست آورد. گراف‌های دزا، (?, µ)-گراف‌ها و گراف‌های تقسیم‌پذیر طرحی سه تعمیم مهم گراف‌های قویاً منظم هستند که در این پایان‌نامه به بررسی نتایج به‌دست آمده در مورد این گراف‌ها می‌پردازیم. در این خصوص (?, µ)-گراف‌ها به‌طور کامل رده‌بندی می‌شوند. هم‌چنین برای ساخت گراف‌های دزا و گراف‌های تقسیم‌پذیر طرحی روش‌هایی ارائه و در چند حالت خاص این گراف‌ها نیز رده‌بندی می‌شوند.

ارتقاء امنیت وب با وف بومی