| Název: | Perfektní párování v regulárních kubických grafech Perfect matchings of regular bipartite graphs |
| Autoři: | Lukoťka, Robert Rollová, Edita |
| Citace zdrojového dokumentu: | LUKOŤKA, R., ROLLOVÁ, E. Perfect matchings of regular bipartite graphs. Journal of Graph Theory>, 2017, roč. 85, č. 2, s. 525-532. ISSN 0364-9024. |
| Datum vydání: | 2017 |
| Nakladatel: | Wiley |
| Typ dokumentu: | článek article |
| URI: | http://hdl.handle.net/11025/29241 |
| ISSN: | 0364-9024 |
| Klíčová slova: | graf, párování |
| Klíčová slova v dalším jazyce: | graph, matching |
| Abstrakt: | Pro regulární bipartitní graf G a X ⊆ E (G) dokážeme, že existuje perfektní párování grafu G obsahující obojí - sudý i lichý počet hran z X tehdy a jenom tehdy kdyź signovaný graf (G,X) není ekvivalentní s (G, ∅). V skutečnosti dokážeme, že pro daný signovaný regulární bipartitní graf s minimální signaturou, je možné najít perfektní párování které obsahuje žádnou nebo právě jednu zvolenou negativní hranu. Navíc když je graf G kubický, tak existuje perfektní párování, které obsahuje právě 2 zvolené hrany. |
| Abstrakt v dalším jazyce: | Let G be a regular bipartite graph and X ⊆ E (G). We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph (G, X ) is not equivalent to (G, ∅). In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge.Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. |
| Práva: | Plný text není přístupný. © Wiley |
| Vyskytuje se v kolekcích: | Články / Articles (KMA) OBD |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| jgt22076.pdf | 102 kB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/29241Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.