| Title: | Perfektní párování v regulárních kubických grafech Perfect matchings of regular bipartite graphs |
| Authors: | Lukoťka, Robert Rollová, Edita |
| Citation: | 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. |
| Issue Date: | 2017 |
| Publisher: | Wiley |
| Document type: | článek article |
| URI: | http://hdl.handle.net/11025/29241 |
| ISSN: | 0364-9024 |
| Keywords: | graf, párování |
| Keywords in different language: | graph, matching |
| Abstract: | 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. |
| Abstract in different language: | 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. |
| Rights: | Plný text není přístupný. © Wiley |
| Appears in Collections: | Články / Articles (KMA) OBD |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| jgt22076.pdf | 102 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/29241Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.