Title: | Closure for {K(1,4),K(1,4)+e}-free graphs |
Other Titles: | Uzávěrová operace pro grafy bez {K(1,4),K(1,4)+e} |
Authors: | Ryjáček, Zdeněk Vrána, Petr Wang, Shipeng |
Citation: | RYJÁČEK, Z., VRÁNA, P., WANG, S. Closure for {K(1,4),K(1,4)+e}-free graphs. Journal of combinatorial theory series, 2019, roč. 134, č. January 2019, s. 239-263. ISSN 0095-8956 |
Issue Date: | 2019 |
Publisher: | Elsevier |
Document type: | článek article |
URI: | http://hdl.handle.net/11025/30750 |
ISSN: | 0095-8956 |
Keywords: | Hamiltonovský graf;uzávěr;graf bez {K(1,4),K(1,4)+e};graf bez K(1,3);hranový graf;Thomassenova hypotéza;podmínka na stupně |
Keywords in different language: | Hamiltonian graph;closure;{K(1,4),K(1,4)+e}-free graph;claw-free graph;line graph;Thomassen’s conjecture;degree condition |
Abstract: | V článku zavádíme uzávěrovou operaci pro grafy bez {K(1,4),K(1,4)+e}, která zobecňuje uzávěrovou operaci pro grafy bez K(1,3). Uzávěr grafu G bez {K(1,4),K(1,4)+e} s minimálním stupněm alespoň 6 je jednoznačně určen, je hranovým grafem hrafu bez trojúhelníků, a zachovává hamiltonovskost či nehamiltononskost grafu G. Jako aplikace ukazujeme, že pomocí uzávěrové operace mohou být mnohé výsledky o grafech bez K(1,3) přímo zobecněny na grafy bez {K(1,4),K(1,4)+e}. |
Abstract in different language: | We introduce a closure concept for hamiltonicity in the class of {K(1,4),K(1,4)+e}-free graphs, extending the closure for claw-free graphs introduced by Ryjáček (1997). The closure of a {K(1,4),K(1,4)+e}-free graph G with minimum degree at least 6 is uniquely determined, is a line graph of a triangle-free graph, and preserves hamiltonicity or non-hamiltonicity of G. As applications, we show that many results on claw-free graphs can be directly extended to the class of {K(1,4),K(1,4)+e}-free graphs. |
Rights: | Plný text není přístupný. © Elsevier |
Appears in Collections: | Články / Articles (KMA) OBD |
Files in This Item:
File | Size | Format | |
---|---|---|---|
1-s2.0-S0095895618300546-main.pdf | 1,36 MB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/30750
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.