Title: | The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs |
Other Titles: | WL-dimenze distančně dědičných grafů |
Authors: | Gavrilyuk, Alexander Nedela, Roman Ponomarenko, Ilia |
Citation: | GAVRILYUK, A. NEDELA, R. PONOMARENKO, I. The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs. GRAPHS AND COMBINATORICS, 2023, roč. 39, č. 4, s. nestránkováno. ISSN: 0911-0119 |
Issue Date: | 2023 |
Publisher: | Springer |
Document type: | článek article |
URI: | 2-s2.0-85165259992 http://hdl.handle.net/11025/53899 |
ISSN: | 0911-0119 |
Keywords: | distančně dědičné grafy;WL-dimenze;isomorfismus grafů |
Keywords in different language: | distance-hereditary graph;Weisfeiler-Leman dimension;graph isomorphism |
Abstract: | Graf nazýváme distančně dědičný když v libovolném souvislém indukovaném podgrafe je vzdálenost dvou vrcholů rovnaká jako v původním grafu. V článku dokážeme, že WL-dimenze distnčně dědičných grafů je dva. |
Abstract in different language: | 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 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. |
Rights: | © The Author(s) |
Appears in Collections: | Články / Articles (NTIS) Články / Articles (KMA) OBD |
Files in This Item:
File | Size | Format | |
---|---|---|---|
WLdimhereditarygraphs.pdf | 349,16 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/53899
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.