| Název: | The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs |
| Další názvy: | WL-dimenze distančně dědičných grafů |
| Autoři: | Gavrilyuk, Alexander Nedela, Roman Ponomarenko, Ilia |
| Citace zdrojového dokumentu: | 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 |
| Datum vydání: | 2023 |
| Nakladatel: | Springer |
| Typ dokumentu: | článek article |
| URI: | 2-s2.0-85165259992 http://hdl.handle.net/11025/53899 |
| ISSN: | 0911-0119 |
| Klíčová slova: | distančně dědičné grafy;WL-dimenze;isomorfismus grafů |
| Klíčová slova v dalším jazyce: | distance-hereditary graph;Weisfeiler-Leman dimension;graph isomorphism |
| Abstrakt: | 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. |
| Abstrakt v dalším jazyce: | 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. |
| Práva: | © The Author(s) |
| Vyskytuje se v kolekcích: | Články / Articles (NTIS) Články / Articles (KMA) OBD |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| WLdimhereditarygraphs.pdf | 349,16 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/53899Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.