✦ LIBER ✦

Toughness, minimum degree, and spanning cubic subgraphs

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

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 197 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20033

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Toughness, minimum degree, and spanning

Toughness, minimum degree, and spanning cubic subgraphs

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

## 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

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