Title: | Stromovité grafy typu snark Treelike snarks |
Authors: | Abreu, Marién Kaiser, Tomáš Labbate, Domenico Mazzuoccolo, Giuseppe |
Citation: | ABREU, M., KAISER, T., LABBATE, D., MAZZUOCCOLO, G. Treelike snarks. Electronic journal of combinatorics, 2016, roč. 23, č. 3, s. 1-19. ISSN: 1077-8926 |
Issue Date: | 2016 |
Publisher: | E-JC |
Document type: | článek article |
URI: | http://hdl.handle.net/11025/29177 |
ISSN: | 1077-8926 |
Keywords: | snark;excesívní index;cirkulární tokové číslo;dvojité pokrytí cykly |
Keywords in different language: | Snark;excessive index;circular flow number;cycle double cover |
Abstract: | V článku studujeme grafy typu snark, jejichž hrany se nedají pokrýt méně než 5 perfektními párováními. Esperet a Mazzuoccolo našli nekonečnou třídu takových grafů a zobecnili tak příklad zkonstruovaný Hägglundem. Ukážeme konstrukci jiné nekonečné třídy, získané zobecněním v odlišném směru. Důkaz, že tato třída má požadovanou vlastnost, používá prohledávání pomocí počítače. Dále ukazujeme, že grafy z této třídy (říkáme jim stromovité grafy typu snark) mají cirkulární tokové číslo $\phi_C (G)\ge5$ a mají dvojité pokrytí 5 cykly. |
Abstract in different language: | We study snarks whose edges cannot be covered by fewer than five perfect matchings. Esperet and Mazzuoccolo found an infinite family of such snarks, generalising an example provided by Hägglund. We construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them \emph{treelike snarks}) have circular flow number $\phi_C (G)\ge5$ and admit a 5-cycle double cover. |
Rights: | © E-JC |
Appears in Collections: | Články / Articles (KMA) OBD |
Files in This Item:
File | Size | Format | |
---|---|---|---|
6008-18625-3-PB.pdf | 366,85 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/29177
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.