Closure and forbidden pairs for 2-factors

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F10%3A00503401" target="_blank" >RIV/49777513:23520/10:00503401 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Closure and forbidden pairs for 2-factors
Original language description
Pairs of connected graphs X,Y such that a graph G is 2-connected and XY-free implies that G is hamiltonian were characterized by Bedrossian. Using the closure concept for claw-free graphs, the first author simplified the characterization by showing thatif considering the closure of G, the list in the Bedrossian characterization can be reduced to one pair, namely, K(1,3) and N(1,1,1). Faudree et al. characterized pairs X,Y such that G is 2-connected and XY-free implies that G has a 2-factor. Recently, the first author et al. strengthened the closure concept for claw-free graphs such that the closure of a graph has stronger properties while still preserving the (non)-existence of a 2-factor. In this paper we show that, using the 2-factor closure, the list of forbidden pairs for 2-factors can be reduced to two pairs, namely, K(1,4), P(4) and K(1,3), N(1,1,3).
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP) Z - Vyzkumny zamer (s odkazem do CEZ) S - Specificky vyzkum na vysokych skolach

Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)