The Weisfeiler-Leman dimension of distance-hereditary graphs

2020/05/24 by Alexander L. Gavrilyuk, Gavrilyuk, Alexander L., Roman Nedela +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2005.11766

arxiv created 2020/05/24 · arxiv updated 2020/05/26

Abstract

A graph is said to be distance-hereditary if the distance function in every connected induced subgraph is the same as in the graph itself. We prove that the ordinary Weisfeiler-Leman algorithm correctly tests the isomorphism of any two graphs if one of them is distance-hereditary; more precisely, the Weisfeiler-Leman dimension of the class of finite distance-hereditary graphs is equal to 2. The previously best known upper bound for the dimension was 7.

Related

• An Upper Bound on the Weisfeiler-Leman Dimension
• Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
• Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm
• A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
• A note on distance-hereditary graphs whose complement is also distance-hereditary