گراف جانسون

گراف جانسون یک نوع خاص از گراف بدون جهت تعریف شده از نظام مجموعه ها است. رئوس گراف جانسون هستند؛ زیرمجموعه از یک مجموعه با ; دو راسی مجاور هستند که تقاطع دو راس (زیر مجموعه) شامل . هر دوی گراف جانسون و جانسون طرح به نام سلمر مارتین جانسون نام گذاری شده است.نبو
یک زیر گروه فاصله-متعدی از هم ریخت به . در واقع ≅ مگر اینکه ; در غیر این صورت ≅ .
به عنوان یک نتیجه از در فاصله-متعدی بودن، همچنین با فاصله منظم بودن . به صورت نمایش داده می شود که در آن:
مگر آنکه ; آرایه تقاطع با سه گراف دیگر با فاصله منظمی که گراف جانسون نباشند به اشتراک گذاشته می شود.