กราฟเอกพันธุ์

ในทางคณิตศาสตร์กราฟk-อัลตราโฮโมจีนัสคือกราฟที่ไอโซมอร์ฟิซึม ทุกตัว ระหว่างกราฟย่อยเหนี่ยวนำ สองตัว ที่มีจุดยอดไม่เกินkจุด สามารถขยายเป็นออโตมอร์ฟิซึมของกราฟทั้งหมดได้ กราฟ k- โฮ โมจีนัสเป็นไปตามคุณสมบัติเดียวกันในรูปแบบที่อ่อนกว่า ซึ่งไอโซมอร์ฟิซึมทุกตัวระหว่างกราฟย่อยเหนี่ยวนำสองตัวบ่งบอกถึงการมีอยู่ของออโตมอร์ฟิซึมของกราฟทั้งหมดที่แมปกราฟย่อยหนึ่งไปยังอีกกราฟย่อยหนึ่ง (แต่ไม่จำเป็นต้องขยายไอโซมอร์ฟิซึมที่กำหนด) [ 1 ]
กราฟเอกพันธุ์คือกราฟที่เป็นk-เอกพันธุ์สำหรับทุกkหรือเทียบเท่ากับk-เอกพันธุ์พิเศษสำหรับทุกkและด้วยเหตุนี้ กราฟเอกพันธุ์ทุกกราฟจึงเป็นเอกพันธุ์พิเศษด้วย[ 1 ]เป็นกรณีพิเศษของแบบจำลองเอกพันธุ์
การจำแนกประเภท
กราฟเอกพันธุ์จำกัดเพียงอย่างเดียวคือกราฟคลัสเตอร์mK ที่สร้างขึ้นจากการรวมแบบไม่ทับซ้อนของกราฟสมบูรณ์ ที่สมมาตรกัน กราฟTuránที่สร้างขึ้นเป็นกราฟส่วนเติมเต็มของmK กราฟเรือ 3 × 3 และวัฏจักร 5 [ 2 ]
กราฟเอกพันธุ์อนันต์ ที่นับได้เพียงอย่างเดียวคือการรวมกันแบบไม่ทับซ้อนของกราฟสมบูรณ์ที่สมมาตรกัน (โดยที่ขนาดของกราฟสมบูรณ์แต่ละกราฟ จำนวนกราฟสมบูรณ์ หรือทั้งสองจำนวนเป็นอนันต์ที่นับได้) กราฟส่วนเติมเต็ม กราฟเฮนสันพร้อมกับกราฟส่วนเติมเต็ม และกราฟราโด[ 3 ]
ถ้ากราฟเป็น 5-อัลตราโฮโมจีนัส แสดงว่ากราฟนั้นเป็นอัลตราโฮโมจีนัสสำหรับทุกkมีเพียง กราฟ เชื่อมต่อ สอง กราฟเท่านั้นที่เป็น 4-อัลตราโฮโมจีนัสแต่ไม่ใช่ 5-อัลตราโฮโมจีนัส ได้แก่กราฟ Schläfliและส่วนเติมเต็มของมัน การพิสูจน์อาศัย การจำแนกกลุ่ม ง่ายจำกัด[ 4 ]
การเปลี่ยนแปลง
กราฟจะเรียกว่าเชื่อมต่อแบบเอกพันธุ์ได้ก็ต่อเมื่อไอโซมอร์ฟิซึมทุกตัวระหว่างกราฟย่อยที่เชื่อมต่อกันสองตัวสามารถขยายไปเป็นออโตมอร์ฟิซึมของกราฟทั้งหมดได้ นอกจากกราฟเอกพันธุ์แล้ว กราฟเชื่อมต่อแบบเอกพันธุ์ที่เชื่อมต่อกันแบบจำกัดยังรวมถึงกราฟวงจร ทั้งหมด กราฟรูคสี่เหลี่ยมทั้งหมดกราฟปีเตอร์เซน และ กราฟเคล็บช์แบบ5-ปกติ[ 5 ]