گراف جانسون

گراف جانسون یک نوع خاص از گراف بدون جهت تعریف شده از نظام مجموعه‌ها است. رئوس گراف جانسون  هستند؛ زیرمجموعه از یک مجموعه با ; دو راسی مجاور هستند که تقاطع دو راس (زیر مجموعه) شامل .. هر دوی گراف جانسون و جانسون طرح به نام سلمر مارتین جانسون نام گذاری شده‌است.
 موارد خاص 
  گراف کامل  است.
  گراف هشت وجهی است.
  گراف مکمل برای گراف پترسن است، بنابراین گراف خط  است. به‌طور کلی، به ازای هر n، گراف جانسون  مکمل گراف نسر 

 ویژگی‌های نظ 
  گراف هم ریخت گراف .
  هر جفت از رئوس که در فاصله  . مسیر همیلتونی
  مسیر همیلتونی است، به این معنی که هر جفت از رئوس، مقصد مسیر همیلتونی را در گراف شکل می‌دهند.More than one of |author-link= and |authorlink= specified (help); More than one of |work= and |journal= specified (help)

.
  .More than one of |last1= and |last= specified (help); More than one of |first1= and |first= specified (help)
  گرافی با رئوس و یال‌ها از چندبری با ابعاد (n - 1) می‌سازد که hypersimplex نام دارد.
 گروهک با کمترین و بیشترین مقدار آن یعنی .
   حداکثر به .

 گروه خودسازی 
یک زیر گروه فاصله-متعدی از هم ریخت  به . در واقع   مگر اینکه ; در غیر این صورت   .

 آرایه تقاطع 
به عنوان یک نتیجه از در فاصله-متعدی بودن، همچنین با فاصله منظم بودن .   به صورت  نمایش داده می‌شود که در آن:
  برای همه .
  برای همه .

مگر آنکه  ; آرایه تقاطع  با سه گراف دیگر با فاصله منظمی که گراف جانسون نباشند به اشتراک گذاشته می‌شود.

 مقادیر ویژه و بردارهای ویژه 
 مشخصه چند جمله ای  به روش زیر به دست می‌آید: .
 این بردارهای ویژه از  توصیف صریحی دارند.

 رابطه با طرح جانسون 
گراف جانسون  رابطه نزدیکی با طرح جانسون دارد، یک طرح انجمنی که در آن هر جفت از k عضو مجموعه در ارتباط با عددی است که نصف اندازه تفاضل متقارن این دو مجموعه است.More than one of |ISBN= and |isbn= specified (help)

. گراف جانسون برای هر جفت از مجموعه‌ها که فاصله آن‌ها در طرح انجمنی یکی است، یک یال دارد، و فواصل در طرح انجمنی دقیقاً کوتاهترین مسیر در گراف جانسون است.The explicit identification of graphs with association schemes, in this way, can be seen in More than one of |work= and |journal= specified (help); More than one of |mr= and |MR= specified (help); More than one of |DOI= and |doi= specified (help)

.

طرح جانسون همچنین با دیگر خانواده‌ها از مسیر-متعدی، گراف‌های فرد که رئوس آن‌ها دارای زیر مجموعه‌هایی با  از مجموعه ای شامل .

 مشکلات حل نشده 
ویژگی‌های گسترش راس از گراف جانسون به خوبی ساختار متناظر مجموعه‌های رئوس از اندازه داده شده، به‌طور کامل قابل فهم نیست. اگرچه، به‌طور متناوب محدوده کوچک‌تر در گسترش مجموعه‌های بزرگ از رئوس، به تازگی به دست آمده‌است.More than one of |last1= and |last= specified (help); More than one of |first1= and |first= specified (help); More than one of |work= and |journal= specified (help)

.

به‌طور کلی، در تعیین تعداد رنگ‌ها برای گراف جانسون یک مشکل حل نشده‌است.

 منابع 

رده:خانواده‌های پارامتری گراف‌ها
رده:صفحه‌های دارای ارجاع با متغیر تکراری
رده:گراف‌های منتظم