กราฟค็อกซ์เตอร์
กราฟค็อกซ์เตอร์
ตั้งชื่อตาม	เอชเอสเอ็ม ค็อกซ์เตอร์
จุดยอด	28
ขอบ	42
รัศมี	4
เส้นผ่านศูนย์กลาง	4
เส้นรอบวง	7
ออโตมอร์ฟิซึม	336 ( PGL 2 (7))
หมายเลขสี	3
ดัชนีสี	3
ความหนาของหนังสือ	3
หมายเลขคิว	2
คุณสมบัติ	สมมาตรระยะทางปกติระยะทางแบบทรานซิทีฟ ลูกบาศก์ไฮโปฮามิลโทเนียน
ตารางกราฟและพารามิเตอร์

ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟCoxeterเป็นกราฟปกติ 3 ที่มีจุดยอด 28 จุดและขอบ 42 เส้น^{[ 1 ]}เป็นหนึ่งในกราฟปกติระยะทางลูกบาศก์ 13 กราฟ ที่รู้จัก ^{[ 2 ]}ตั้งชื่อตามHarold Scott MacDonald Coxeter

กราฟ Coxeter มีจำนวนสี 3, ดัชนีสี 3, รัศมี 4, เส้นผ่านศูนย์กลาง 4 และเส้นรอบวง 7 นอกจากนี้ยังเป็นกราฟที่เชื่อมต่อจุดยอด 3 จุด และเชื่อมต่อขอบ 3 เส้น มีความหนาของหนังสือ 3 และจำนวนคิว 2 ^{[ 3 ]}

กราฟ Coxeter เป็นกราฟไฮโปแฮมิลโทเนียน : ตัวมันเองไม่มีวัฏจักรแฮมิลโทเนียน แต่กราฟทุกกราฟที่เกิดจากการลบจุดยอดเพียงจุดเดียวออกจากกราฟนี้จะเป็นกราฟแฮมิลโทเนียน มีจำนวนจุดตัดเชิงเส้นตรงเท่ากับ 11 และเป็นกราฟลูกบาศก์ที่เล็กที่สุดที่มีจำนวนจุดตัดดังกล่าว^{[ 4 ]} (ลำดับA110507ในOEIS ) กราฟนี้เป็น กราฟ ระนาบ1 ^{[ 5 ]}

การสร้างกราฟ Coxeter ที่ง่ายที่สุดคือการสร้างจากระนาบ Fanoพิจารณาการจัดเรียง 3 มิติที่เป็นไปได้⁷ C ₃ = 35 แบบ บนวัตถุ 7 ชิ้น ทิ้งชุดสามชิ้น 7 ชุดที่สอดคล้องกับเส้นของระนาบ Fano เหลือชุดสามชิ้น 28 ชุด เชื่อมโยงชุดสามชิ้นสองชุดเข้าด้วยกันหากชุดเหล่านั้นไม่ทับซ้อนกัน ผลลัพธ์ที่ได้คือกราฟ Coxeter (ดูภาพประกอบ )การสร้างนี้แสดงให้เห็นกราฟ Coxeter เป็นกราฟย่อยที่เหนี่ยวนำของกราฟคี่ O ₄หรือ ที่รู้จักกันในชื่อกราฟ Kneser KG _7,3

นอกจากนี้ กราฟ Coxeter ยังสามารถสร้างจากกราฟ Heawood ระยะทางปกติที่เล็กกว่าได้ โดยการสร้างจุดยอดสำหรับแต่ละ 6-cycle ในกราฟ Heawood และขอบสำหรับแต่ละคู่ของ 6-cycle ที่ไม่ทับซ้อนกัน^{[ 6 ]}

กราฟ Coxeter สามารถสร้างขึ้นได้จากกราฟ Hoffman-Singletonพิจารณาจุดยอดv ใดๆ ในกราฟ Hoffman-Singleton จะมีเซตอิสระขนาด 15 ที่รวมv อยู่ด้วย ลบจุดยอดข้างเคียง 7 จุดของvและเซตอิสระทั้งหมดที่รวมv อยู่ด้วย จะเหลือไว้ซึ่งกราฟ Coxeter

กลุ่มออโตมอร์ฟิซึมของกราฟ Coxeter เป็นกลุ่มที่มีอันดับ 336 ^{[ 7 ]}มันกระทำการทรานซิทีฟบนจุดยอด บนขอบ และบนส่วนโค้งของกราฟ ดังนั้น กราฟ Coxeter จึงเป็นกราฟสมมาตรมันมีออโตมอร์ฟิซึมที่นำจุดยอดใดๆ ไปยังจุดยอดอื่นๆ และขอบใดๆ ไปยังขอบอื่นๆ ตามการสำรวจของ Fosterกราฟ Coxeter ซึ่งอ้างอิงเป็น F28A เป็นกราฟสมมาตรลูกบาศก์เพียงกราฟเดียวที่มี 28 จุดยอด^{[ 8 ]}

กราฟ Coxeter ยังถูกกำหนดอย่างเป็นเอกลักษณ์โดยสเปกตรัมกราฟ ซึ่ง ^เป็นเซตของค่าลักษณะเฉพาะของกราฟของเมทริกซ์ประชิด [ ^{9 ]}

กราฟ Coxeter เป็นกราฟเชื่อมต่อที่มีขอบเขตจำกัดและมีคุณสมบัติการสลับจุดยอด ซึ่งไม่มีวัฏจักรแฮมิลโทเนียน จึง เป็นตัวอย่างค้านสำหรับทฤษฎีบท Lovász รูป แบบหนึ่ง แต่สูตรมาตรฐานของทฤษฎีบทนี้ต้องการเส้นทางแฮมิลโทเนียน และได้รับการยืนยันโดยกราฟ Coxeter

มีเพียงตัวอย่างกราฟแบบ vertex-transitive ที่ไม่มีวงจรแฮมิลโทเนียนเพียงห้าตัวอย่างเท่านั้นที่เป็นที่รู้จัก ได้แก่กราฟสมบูรณ์K ₂กราฟPetersenกราฟ Coxeter และกราฟสองกราฟที่ได้มาจากกราฟ Petersen และ Coxeter โดยการแทนที่จุดยอดแต่ละจุดด้วยรูปสามเหลี่ยม^{[ 10 ]}

พหุนามลักษณะเฉพาะของกราฟค็อกซ์เตอร์คือ. เป็นกราฟเพียงกราฟเดียวที่มีพหุนามลักษณะเฉพาะนี้ ทำให้เป็นกราฟที่ถูกกำหนดโดยสเปกตรัมของมัน ${\displaystyle (x-3)(x-2)^{8}(x+1)^{7}(x^{2}+2x-1)^{6}}$

นี่คือภาพแสดงกราฟ Coxeter ในรูปแบบต่างๆ โดยใช้ป้ายกำกับจุดยอดเดียวกัน มีสี่สี และแต่ละสีมีจุดยอดเจ็ดจุด จุด ยอดสีแดง สีเขียว หรือสีน้ำเงินแต่ละจุดเชื่อมต่อกับจุดยอดสีเดียวกันสองจุด (ขอบบางๆ ที่ก่อให้เกิดวงจร 7 จุด) และเชื่อมต่อกับจุดยอดสีขาวหนึ่งจุด (ขอบหนา)

รูปเจ็ดเหลี่ยมสีแดง รูปเจ็ดเหลี่ยม มุมป้านสีเขียว และรูปเจ็ด เหลี่ยมมุมแหลมสีน้ำเงิน ด้านซ้าย: สมมาตรการหมุน 7 เท่า