Minimal graph in which the intersection of two longest paths is not a separator

2021/05/25 by Juan Gutiérrez, Gutiérrez, Juan, Christian Valqui +1
Computer Science · Mathematics · #05C38 (Primary) 05C45 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2105.11633

openalex publication_date 2021/05/25 · openalex created_date 2021/06/07 · openalex updated_date 2026/07/28

Abstract

We prove that for a connected simple graph G with n≤ 10 vertices, and two longest paths C and D in G, the intersection of vertex sets V(C)∩ V(D) is a separator. This shows that the graph found previously with n=11, in which the complement of the intersection of vertex sets V(C)∩ V(D) of two longest paths is connected, is minimal.

Related

• Minimal Separators in Graphs
• A Characterization of all Stable Minimal Separator Graphs
• Nonempty intersection of longest paths in 2K₂-free graphs
• Separating paths systems of almost linear size
• Separating path systems