✦ LIBER ✦

Toughness, minimum degree, and spanning cubic subgraphs

✍ Scribed by D. Bauer; T. Niessen; E. Schmeichel

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 189 KB
Volume: 45
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10149

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Degree conditions on the vertices of a t‐tough graph G (1 ≤ t < 3) are presented which ensure the existence of a spanning cubic subgraph in G. These conditions are best possible to within a small additive constant for every fixed rational t ∈[1,4/3)∪[2,8/3). © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 119–141, 2004

📜 SIMILAR VOLUMES

Toughness, minimum degree, and spanning

Toughness, minimum degree, and spanning cubic subgraphs

✍ D. Bauer; T. Niessen; E. Schmeichel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

The electronic version has been replaced with the correct figures; the corrected print version follows. The article originally posted in Wiley InterScience is available from the publisher should anyone require access to it. We regret any inconvenience this may have caused.

Average distance, minimum degree, and sp

Average distance, minimum degree, and spanning trees

✍ Dankelmann, Peter; Entringer, Roger 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 218 KB

The average distance µ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., µ(G) = ( n 2 ) -1 {x,y}⊂V (G) d G (x, y), where V (G) denotes the vertex set of G and d G (x, y) is the distance between x and y. We prove that every connected graph

Light subgraphs in planar graphs of mini

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9

✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

Lower and upper bounds for the degree-co

Lower and upper bounds for the degree-constrained minimum spanning tree problem

✍ Alexandre Salles da Cunha; Abilio Lucena 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

Models and heuristics for the k -degree

Models and heuristics for the k -degree constrained minimum spanning tree problem with node-degree costs

✍ Christophe Duhamel; Luís Gouveia; Pedro Moura; Maurício de Souza 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

## Abstract The __k__ ‐Degree constrained Minimum Spanning Tree Problem (__k__ ‐DMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value __k__. Here we consider an extension where besides the edge costs, a concave co

A branch and cut method for the degree-c

A branch and cut method for the degree-constrained minimum spanning tree problem

✍ L. Caccetta; S.P. Hill 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 2 views