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 B, 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}.
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.
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 SizeFormat 
1-s2.0-S0095895618300546-main.pdf1,36 MBAdobe PDFView/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.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD