กราฟสีเทา
กราฟสีเทา
ตั้งชื่อตาม	มาริออน คาเมรอน เกรย์
จุดยอด	54
ขอบ	81
รัศมี	6
เส้นผ่านศูนย์กลาง	6
เส้นรอบวง	8
ออโตมอร์ฟิซึม	1296
หมายเลขสี	2
ดัชนีสี	3
ประเภท	7
ความหนาของหนังสือ	3
หมายเลขคิว	2
คุณสมบัติ	แฮมิลโทเนียนแบบลูกบาศก์กึ่งสมมาตรแบบ สอง ส่วน
ตารางกราฟและพารามิเตอร์

ในสาขาคณิตศาสตร์ทฤษฎีกราฟ กราฟเกรย์เป็นกราฟสองส่วนแบบไม่มี ทิศทาง ที่มี 54 จุดยอดและ 81 ขอบเป็นกราฟลูกบาศก์ กล่าว คือ ทุกจุดยอดสัมผัสกับขอบสามเส้นพอดี กราฟนี้ถูกค้นพบโดยMarion C. Grayในปี 1932 (ไม่ได้ตีพิมพ์) จากนั้น Bouwer ค้นพบโดยอิสระในปี 1968 เพื่อตอบคำถามที่Jon Folkman ตั้งขึ้น ในปี 1967 กราฟเกรย์น่าสนใจตรงที่เป็นตัวอย่างแรกที่รู้จักของกราฟลูกบาศก์ที่มีคุณสมบัติทางพีชคณิตคือ ขอบสามารถถ่ายทอดได้ แต่จุดยอดไม่สามารถถ่ายทอดได้ (ดูด้านล่าง)

กราฟเกรย์มีจำนวนสี 2, ดัชนีสี 3, รัศมี 6 และเส้นผ่านศูนย์กลาง 6 นอกจากนี้ยังเป็นกราฟที่ไม่ระนาบซึ่งเชื่อมต่อจุดยอด 3 จุด และเชื่อมต่อขอบ 3 จุด ด้วย

ตารางขนาด 3 × 3 × 3 ซึ่งความสัมพันธ์ระหว่างจุดและเส้นนั้นอธิบายได้ด้วยกราฟเกรย์    

กราฟที่มีจุดยอดเรียงและระบายสีตามตำแหน่งในตาราง

กราฟนี้เป็นกราฟระยะทางหน่วยที่มีสมมาตรการหมุน 3 เท่า

กราฟเกรย์สามารถสร้างขึ้นได้( Bouwer 1972 )จากจุด 27 จุดของตาราง 3 × 3 × 3 และเส้นขนานแกน 27 เส้นที่ลากผ่านจุดเหล่านี้ ชุดของจุดและเส้นเหล่านี้ก่อให้เกิดโครงสร้างเชิงโปรเจคทีฟ : แต่ละจุดมีเส้นผ่านสามเส้นพอดี และแต่ละเส้นมีจุดสามจุดอยู่บนเส้นนั้นพอดี กราฟเกรย์คือกราฟเลวีของโครงสร้างนี้ มันมีจุดยอดสำหรับทุกจุดและทุกเส้นของโครงสร้าง และมีขอบสำหรับทุกคู่ของจุดและเส้นที่สัมผัสกัน การสร้างนี้สามารถขยายได้ (Bouwer 1972) ไปยังมิติใดๆn ≥ 3 ทำให้ได้ กราฟเลวี n -valent ที่มีคุณสมบัติทางพีชคณิตคล้ายกับกราฟเกรย์ ใน (Monson, Pisanski, Schulte, Ivic-Weiss 2007) กราฟเกรย์ปรากฏเป็นกราฟเลวีอีกแบบหนึ่งสำหรับขอบและหน้าสามเหลี่ยมของโพลีโทป 4 มิติปกติแบบนามธรรมที่มีลักษณะเป็นทรงกลมเฉพาะที่ ดังนั้นจึงเป็นกราฟลูกบาศก์แรกในตระกูลอนันต์ของกราฟลูกบาศก์ที่มีโครงสร้างคล้ายกัน เช่นเดียวกับกราฟ Levi อื่นๆ กราฟนี้เป็นกราฟสองส่วนโดยจุดยอดจะสอดคล้องกับจุดบนด้านหนึ่งของการแบ่งสองส่วน และจุดยอดจะสอดคล้องกับเส้นตรงบนอีกด้านหนึ่ง    

MarušičและPisanski (2000) เสนอวิธีการสร้างกราฟ Gray หลายวิธี เช่นเดียวกับกราฟสองส่วนใดๆ กราฟ Gray จะไม่มีวัฏจักร ที่มีความยาวเป็นเลขคี่ และไม่มีวัฏจักรที่มีสี่หรือหกจุดยอด ดังนั้นเส้นรอบวง ของกราฟ Gray จึงเท่ากับ 8 พื้นผิวที่กำหนดทิศทางที่ง่ายที่สุดที่สามารถ ฝังกราฟ Gray ได้นั้นมีจีนัสเท่ากับ 7 ( Marušič, Pisanski & Wilson 2005 )

กราฟเกรย์เป็นกราฟแฮมิลโทเนียนและสามารถสร้างได้จากสัญลักษณ์ LCF :

${\displaystyle [-25,7,-7,13,-13,25]^{9}.\ }$

เนื่องจากเป็นกราฟลูกบาศก์แฮมิลโทเนียน จึงมีดัชนีสีเท่ากับสาม

กลุ่มออโตมอร์ฟิซึมของกราฟเกรย์เป็นกลุ่มที่มีอันดับ 1296 มันกระทำการทรานซิทีฟบนขอบของกราฟแต่ไม่กระทำการทรานซิทีฟบนจุดยอด: มีสมมาตรที่เชื่อมโยงทุกขอบกับขอบอื่น ๆ ได้ แต่ไม่มีสมมาตรที่เชื่อมโยงทุกจุดยอดกับจุดยอดอื่น ๆ ได้ จุดยอดที่สอดคล้องกับจุดในโครงสร้างพื้นฐานจะสมมาตรกับจุดยอดอื่น ๆ ที่สอดคล้องกับจุดเท่านั้น และจุดยอดที่สอดคล้องกับเส้นจะสมมาตรกับจุดยอดอื่น ๆ ที่สอดคล้องกับเส้นเท่านั้น ดังนั้น กราฟเกรย์จึงเป็นกราฟกึ่งสมมาตรซึ่งเป็นกราฟกึ่งสมมาตรลูกบาศก์ที่เล็กที่สุดที่เป็นไปได้

พหุนามลักษณะเฉพาะของกราฟเกรย์คือ

${\displaystyle (x-3)x^{16}(x+3)(x^{2}-6)^{6}(x^{2}-3)^{12}.\ }$

กราฟเกรย์สามารถแสดงด้วยจุดในระนาบในลักษณะที่จุดยอดที่อยู่ติดกันมีระยะห่างหนึ่งหน่วย นั่นคือเป็นกราฟ ระยะทางหน่วย^{[ 1 ]}

• ไวส์สไตน์, เอริค ดับเบิลยู. "กราฟสีเทา" . แมธเวิลด์ .
• กราฟสีเทาเป็นกราฟที่เล็กที่สุดในประเภทเดียวกันจากMathWorld