گراف جانسون

گراف جانسون یک نوع خاص از گراف بدون جهت تعریف شده از نظام مجموعه ها است. رئوس گراف جانسون هستند؛ زیرمجموعه از یک مجموعه با ; دو راسی مجاور هستند که تقاطع دو راس ( زیر مجموعه ) شامل . [ ۱] هر دوی گراف جانسون و جانسون طرح به نام سلمر مارتین جانسون نام گذاری شده است.
• {\displaystyle } گراف کامل Kn است.
• {\displaystyle } گراف هشت وجهی است.
• {\displaystyle } گراف مکمل برای گراف پترسن است، بنابراین گراف خط K5 است. به طور کلی، به ازای هر n، گراف جانسون {\displaystyle } مکمل گراف نسر {\displaystyle }
• J ( n , k ) {\displaystyle J ( n, k ) } گراف هم ریخت گراف J ( n , n − k ) {\displaystyle J ( n, n - k ) } .
• 0 ≤ j ≤ d i a m ( J ( n , k ) ) {\displaystyle 0\leq j\leq \mathrm {diam} ( J ( n, k ) ) } هر جفت از رئوس که در فاصله j {\displaystyle j} k − j {\displaystyle k - j} . مسیر همیلتونی
• J ( n , k ) {\displaystyle J ( n, k ) } مسیر همیلتونی است، به این معنی که هر جفت از رئوس، مقصد مسیر همیلتونی را در گراف شکل می دهند. [ ۲]
• J ( n , k )   {\displaystyle J ( n, k )
}   k ( n − k ) {\displaystyle
k ( n - k ) } . [ ۳]
• J ( n , k ) {\displaystyle J ( n, k ) } گرافی با رئوس و یال ها از چندبری با ابعاد ( n - 1 ) می سازد که hypersimplex نام دارد. [ ۴]
• ω ( J ( n , k ) ) = 1 − λ m a x λ m i n {\displaystyle \omega \left ( J ( n, k ) \right ) =1 - {\frac {\lambda _{\mathrm {max} }}{\lambda _{\mathrm {min} }}}} گروهک J ( n , k ) {\displaystyle J ( n, k ) } با کمترین و بیشترین مقدار آن یعنی λ m i n {\displaystyle \lambda _{\mathrm {min} }} λ m a x {\displaystyle \lambda _{\mathrm {max} }} .
• χ ( J ( n , k ) ) ≤ n {\displaystyle \chi ( J ( n, k ) ) \leq n} J ( n , k ) {\displaystyle J ( n, k ) } حداکثر به n {\displaystyle n} . [ ۵]
یک زیر گروه فاصله - متعدی از هم ریخت به . در واقع ≅ مگر اینکه ; در غیر این صورت ≅ . [ ۶]
به عنوان یک نتیجه از در فاصله - متعدی بودن، همچنین با فاصله منظم بودن . به صورت نمایش داده می شود که در آن:
• {\displaystyle } برای همه {\displaystyle } .
• {\displaystyle } برای همه {\displaystyle } .