Paths and cycles concerning independence edges
type: Item
instance of: scholarly article
title: Paths and cycles concerning independence edges
zbMATH Open document ID: 0723.05075
DOI: 10.1007/BF01787702
author: Atsushi Kaneko
published in: Graphs and Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: A natural generalization of the concept of alternating path for a matching is that of an admissible path. An admissible path or cycle D in a graph G for a set L of pairwise independent edges is one in which, whenever \(e\in L\), D either contains e or touches no vertex of e. This paper gives a necessary and sufficient condition for a connected graph G to have an admissible path connecting two given vertices for such L. An analogous theorem gives the result for the case when g is 2- connected. The proofs require q pages of supplemental concepts and lemmas. Using these results, the author is able to prove Tutte's 1-factor theorem as well as extensions of two theorems of Lovász on admissible cycles. As another application, the author shows that if G is a 3-regular graph with a Hamiltonian cycle H, then, given any edge of H, there is an admissible cycle for \(L=E(G)-E(H)\) in G through that edge.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4191704
zbMATH Keywords: admissible path
zbMATH Keywords: Tutte's 1-factor theorem
zbMATH Keywords: admissible cycle
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q4830805
cites work: Any four independent edges of a 4-connected graph are contained in a circuit
cites work: On factorisation of graphs
cites work: Circuits through specified edges
cites work: The Two-Triangle Case of the Acquaintance Graph
cites work: Q3880849
cites work: Applications of Menger's graph theorem
cites work: The Factorization of Linear Graphs
cites work: The Factors of Graphs
cites work: Q3216652
cites work: Circuits containing specified edges
full work available at URL: https://doi.org/10.1007/bf01787702
OpenAlex ID: W1991268275
description: scientific article; zbMATH DE number 4191704