Avoiding 7-circuits in 2-factors of cubic graphs
type: Item
instance of: scholarly article
title: Avoiding 7-circuits in 2-factors of cubic graphs
zbMATH Open document ID: 1302.05145
published in: The Electronic Journal of Combinatorics
publication date: 2014-11-13T00:00:00Z
full work available at URL: v21i4p25
review text: Summary: Let \(G\) be a cyclically 4-edge-connected cubic graph with girth at least 7 on \(n\) vertices. We show that \(G\) has a 2-factor \(F\) such that at least a linear amount of vertices is not in 7-circuits of \(F\). More precisely, there are at least \(n/657\) vertices of \(G\) that are not in 7-circuits of \(F\). If \(G\) is cyclically 6-edge-connected then the bound can be improved to \(n/189\). As a corollary we obtain bounds on the oddness and on the length of the shortest travelling salesman tour in a cyclically 4-edge-connected (6-edge-connected) cubic graph of girth at least 7.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6369271
zbMATH Keywords: cubic graphs
zbMATH Keywords: 2-factors
author: R. Lukot'ka
MaRDI profile type: Publication
cites work: The traveling salesman problem on cubic and subcubic graphs
cites work: Q3374865
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: On 2-factors with long cycles in cubic graphs
description: scientific article; zbMATH DE number 6369271