| 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/53899Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.