Internally 4-connected Graphs with no {Cube, V8}-Minor

Chanun Lewchalermvongs, Nawarat Ananchuen

Graph theory is a branch in mathematics concerning the study of graphs, which are composed of vertices and edges connecting two vertices together. It is a tool for formulating problems and explaining basic interrelationships. It is also an important topic in network theory and artificial intelligence that are essential keys in developing many industries. Discovering and understanding more facts in graph theory help us to create more graph theoretical tools that can be used to solve real world problems. In graph theory, a graph H is a minor of a graph G if H is obtained from G by a (possibly empty) sequence of vertex deletions, edge deletions, and edge contractions (where the order of the graph operations is irrelevant). A cube, or a cubical graph, is the Platonic graph corresponding to the connectivity of the cube and the Wagner graph V8 is a graph obtained from a cube by introducing a twist. In this research, we want to characterize all internally 4-connected graphs that do not contain cube as a minor.

ทฤษฎีกราฟเป็นสาขาหนึ่งในคณิตศาสตร์ที่ศึกษาเกี่ยวกับกราฟ ซึ่งประกอบไปด้วยจุดยอดและเส้นเชื่อมที่เชื่อมจุดยอดสองจุดเข้าด้วยกัน ทฤษฎีกราฟเป็นเครื่องมือที่ถูกใช้ในการจำลองปัญหาและอธิบายความสัมพันธ์พื้นฐานที่เกิดขึ้น ยิ่งกว่านั้นทฤษฎีกราฟยังเป็นหัวข้อที่สำคัญในการศึกษาด้านทฤษฎีโครงข่ายและปัญญาประดิษฐ์ซึ่งเป็นกุญแจสำคัญในการพัฒนาด้านอุตสาหกรรม การค้นพบและเข้าใจความจริงในทฤษฎีกราฟช่วยให้เราสามารถสร้างเครื่องมือทางทฤษฎีกราฟที่สามารถถูกใช้ในการแก้ปัญหาจริงในโลกได้ ในทฤษฎีกราฟ กราฟ H เป็นกราฟย่อยของกราฟ G ถ้า H สามารถได้จาก G โดยการลบจุดยอด ลบเส้นเชื่อม และ หดเส้นเชื่อม โดยลำดับไม่มีผล กราฟลูกบาศก์เป็นกราฟพเลโทที่สัมพันธ์กับการเชื่อมโยงของลูกบาศก์ ส่วนกราฟ V8 เป็นกราฟที่ได้จากกราฟลูกบาศก์โดยการสลับเส้นเชื่อมหนึ่งคู่ ในงานวิจัยนี้จะอธิบายลักษณะของกราฟที่ต่อเนื่อง 4 แบบภายในที่ไม่มีกราฟลูกบาศก์ และกราฟ V8 เป็นกราฟย่อย