กราฟจอห์นสัน
กราฟจอห์นสันJ (5,2)
ตั้งชื่อตาม	เซลเมอร์ เอ็ม. จอห์นสัน
จุดยอด	${\displaystyle {\binom {n}{k}}}$
ขอบ	${\displaystyle {\frac {1}{2}}k(nk){\binom {n}{k}}}$
เส้นผ่านศูนย์กลาง	${\displaystyle \min(k,nk)}$
คุณสมบัติ	${\displaystyle k(nk)}$- รูปหลายเหลี่ยมที่เชื่อมต่อแบบแฮมิลตัน และจุด ยอดปกติ ที่ถ่ายทอด ได้ ระยะทาง ที่ถ่ายทอดได้
สัญกรณ์	${\displaystyle J(n,k)}$
ตารางกราฟและพารามิเตอร์

ในทางคณิตศาสตร์กราฟจอห์นสัน เป็น กราฟแบบไม่มีทิศทางประเภทพิเศษที่กำหนดจากระบบของเซต จุดยอดของกราฟจอห์นสันคือ เซตย่อย ที่มีสมาชิกจำนวน n ตัวของเซตที่มีสมาชิกจำนวน n ตัว จุดยอดสองจุดจะอยู่ติดกันเมื่อจุดตัดของจุดยอดทั้งสอง (เซตย่อย) มีสมาชิกจำนวน n ตัว ^{[ 1 ]}ทั้งกราฟจอห์นสันและโครงร่างจอห์นสัน ที่เกี่ยวข้องอย่างใกล้ชิดได้ รับการตั้งชื่อตามเซลเมอร์ เอ็ม. จอห์นสัน ${\displaystyle J(n,k)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle (k-1)}$

• และต่างก็เป็นกราฟสมบูรณ์K _n${\displaystyle J(n,1)}$${\displaystyle J(n,n-1)}$
• ${\displaystyle J(4,2)}$คือกราฟทรงแปดเหลี่ยม^{[ 2 ]}
• ${\displaystyle J(5,2)}$เป็นส่วนเติมเต็มของกราฟ Petersen [ ^{1 ]}ดังนั้นกราฟเส้นของK ₅โดยทั่วไปแล้ว สำหรับทุกกราฟ Johnson เป็นกราฟเส้นของK _nและเป็นส่วนเติมเต็มของ^กราฟ Kneser${\displaystyle n}$${\displaystyle J(n,2)}$${\displaystyle K(n,2).}$

• ${\displaystyle J(n,k)}$มีโครงสร้างเหมือนกับ${\displaystyle J(n,n-k).}$
• สำหรับทุกค่าจุดยอดคู่ใดๆ ที่อยู่ห่างกันเป็นระยะทางจะมีองค์ประกอบร่วมกัน${\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))}$${\displaystyle j}$${\displaystyle k-j}$
• ${\displaystyle J(n,k)}$เป็นกราฟที่เชื่อมต่อแบบแฮมิลตันหมายความว่าจุดยอดทุกคู่จะก่อให้เกิดจุดปลายของเส้นทางแฮมิลตันในกราฟ โดยเฉพาะอย่างยิ่งหมายความว่ากราฟนี้มีวัฏจักรแฮมิลตัน^{[ 3 ]}
• เป็นที่ทราบกันดีว่ากราฟจอห์นสันเป็นกราฟที่เชื่อมต่อจุดยอด^{[ 4 ]}${\displaystyle J(n,k)}$${\displaystyle k(n-k)}$
• ${\displaystyle J(n,k)}$สร้างกราฟจุดยอด-ขอบ ของ โพลีโทป มิติ ( n  − 1) ที่เรียกว่าไฮเปอร์ซิมเพล็กซ์^{[ 5 ]}
• กลุ่มคลิกสูงสุดใดๆจะอยู่ในรูปแบบสำหรับเซตย่อยที่มีสมาชิก - และหรืออยู่ในรูปแบบสำหรับเซตที่มีสมาชิก - สำหรับหรืออยู่ในรูปแบบในกรณีขอบ^{[ 6 ]}${\displaystyle \{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}}$${\displaystyle (k-1)}$${\displaystyle S}$${\displaystyle k<n-1}$${\displaystyle \{S\setminus \{x\}\mid x\in S\}}$${\displaystyle (k+1)}$${\displaystyle S}$${\displaystyle k>1}$${\displaystyle \{\{1\},\{2\}\}}$${\displaystyle (n,k)=(2,1)}$
• จำนวนคลิกของ เมทริก ซ์กำหนดโดยนิพจน์ในรูปของค่าไอเกน ที่น้อยที่สุดและมากที่สุด : หรือโดยคำอธิบายที่ชัดเจนเกี่ยวกับคลิกสูงสุดข้างต้น${\displaystyle J(n,k)}$${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }}$${\displaystyle \omega (J(n,k))=\max\{k+1,N-k+1\}.}$
• จำนวนกลุ่มที่ตรงตามข้อกำหนดสำหรับและสำหรับแต่โดย ทั่วไป แล้วไม่ทราบ^{[ 7 ]}${\displaystyle J(n,k)}$${\displaystyle \theta (J(n,1))=1}$${\displaystyle n>1}$${\displaystyle \theta (J(n,2))=n-2}$${\displaystyle n>2}$${\displaystyle \theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor }$${\displaystyle n>5}$
• จำนวนสีโครมาติกมีค่าสูงสุด^{[ 8 ]}${\displaystyle J(n,k)}$${\displaystyle n,\chi (J(n,k))\leq n.}$
• กราฟจอห์นสันแต่ละกราฟเป็นกริดท้องถิ่นซึ่งหมายความว่ากราฟย่อยที่เหนี่ยวนำของเพื่อนบ้านของจุดยอดใดๆ จะเป็นกราฟของหมากรุกกล่าวคือ ในกราฟจอห์นสันเพื่อนบ้านแต่ละแห่งจะเป็นกราฟของหมากรุก^{[ 9 ]}${\displaystyle J(n,k)}$${\displaystyle k\times (n-k)}$

มีกลุ่มย่อยที่ถ่ายทอดระยะทาง ซึ่งสมมาตรกับ ในความ ^เป็นจริง^{ยกเว้น}เมื่อ[ 10 ^]${\displaystyle \operatorname {Aut} (J(n,k))}$${\displaystyle \operatorname {Sym} (n)}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$${\displaystyle n=2k\geq 4}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$

เนื่องจากมีคุณสมบัติการถ่ายทอดตามระยะทางจึงเป็นเมทริกซ์ปกติตามระยะทาง ด้วย ให้แทนเส้นผ่านศูนย์กลางอาร์เรย์จุดตัดของจะกำหนดโดย ${\displaystyle J(n,k)}$${\displaystyle d}$${\displaystyle J(n,k)}$

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

ที่ไหน:

${\displaystyle {\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}}$

ปรากฏว่าเว้นแต่จะเป็นอาร์เรย์จุดตัดจะไม่ถูกแชร์กับกราฟระยะทางปกติที่แตกต่างกันอื่นใด อาร์เรย์จุดตัดของถูกแชร์กับกราฟระยะทางปกติอื่นอีกสามกราฟที่ไม่ใช่กราฟจอห์นสัน^{[ 1 ]}${\displaystyle J(n,k)}$${\displaystyle J(8,2)}$${\displaystyle J(8,2)}$

• พหุนามลักษณะเฉพาะของกำหนดโดย${\displaystyle J(n,k)}$

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

โดยที่^{[ 10 ]}${\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.}$

• เวกเตอร์ลักษณะเฉพาะของมีคำอธิบายที่ชัดเจน^{[ 11 ]}${\displaystyle J(n,k)}$

กราฟจอห์นสันมีความเกี่ยวข้องอย่างใกล้ชิดกับโครงร่างจอห์นสัน ซึ่ง เป็นโครงร่างการเชื่อมโยงที่แต่ละคู่ของ เซตที่มี kองค์ประกอบจะเชื่อมโยงกับตัวเลขที่มีขนาดครึ่งหนึ่งของผลต่างสมมาตรของเซตทั้งสอง^{[ 12 ]}กราฟจอห์นสันมีขอบสำหรับทุกคู่ของเซตที่มีระยะทางหนึ่งในโครงร่างการเชื่อมโยง และระยะทางในโครงร่างการเชื่อมโยงคือ ระยะทาง เส้นทางที่สั้นที่สุดในกราฟจอห์นสันพอดี^{[ 13 ]}${\displaystyle J(n,k)}$

แผนการของจอห์นสันยังเกี่ยวข้องกับกราฟแบบส่งผ่านระยะทางอีกตระกูลหนึ่ง คือกราฟคี่ซึ่งจุดยอดเป็น เซตย่อยที่ มีสมาชิกจำนวน n ตัวของเซตที่มีสมาชิกจำนวน n ตัว และขอบของกราฟจะสอดคล้องกับคู่ของเซตย่อยที่ไม่ซ้ำกัน^{[ 12 ]}${\displaystyle k}$${\displaystyle (2k+1)}$

คุณสมบัติการขยายจุดยอดของกราฟจอห์นสัน รวมถึงโครงสร้างของเซตจุดยอดสุดขั้วที่สอดคล้องกันที่มีขนาดที่กำหนด ยังไม่เป็นที่เข้าใจอย่างสมบูรณ์ อย่างไรก็ตาม ขอบเขตล่างที่แน่นหนาในเชิงอะซิมโทติกสำหรับการขยายเซตจุดยอดขนาดใหญ่เพิ่งได้รับเมื่อเร็ว ๆ นี้^{[ 14 ]}

โดยทั่วไป การหาจำนวนสีของกราฟจอห์นสันถือเป็นปัญหาที่ยังแก้ไม่ตก^{[ 15 ]}

• กราฟกราสส์มันน์

• ไวส์สไตน์, เอริค ดับเบิลยู. , "กราฟจอห์นสัน" , MathWorld
• บราวเวอร์, แอนดรีส์ อี. , กราฟจอห์นสัน