𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cycles containing all vertices of maximum degree

✍ Scribed by H. J. Broersma; J. Den Van Heuvel; H. A. Jung; H. J. Veldman

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
539 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graph G and an integer k, denote by V~k~ the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2‐connected graph of order n with n ≤ 3k ‐ 2 and |V~k~| ≤ k, then G has a cycle containing all vertices of V~k~. It is shown that the upper bound k on |V~k~| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V~k~| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ __2__δ(G) + δ(G) + 1. This result is an almost‐generalization of Jackson's Theorem that every 2‐connected k‐regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Cycles through vertices of large maximum
Cycles through vertices of large maximum degree
✍ Bill Jackson 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 442 KB

## Abstract Let __G__ be a 2‐connected graph on __n__ vertices with maximum degree __k__ where __n__ ≤ 3__k__ ‐ 2. We show that there is a cycle in __G__ that contains all vertices of degree __k.__ © 1995 John Wiley & Sons, Inc.

Cycles containing many vertices of large
Cycles containing many vertices of large degree
✍ H.J. Veldman 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 446 KB

Veldman, H.J., Cycles containing many vertices of large degree, Discrete Mathematics 101 (1992) 319-325. Let G be a 2-connected graph of order n, r a real number and V, = {u E V(G) ( d(v) 3 r}.

Cycles through Large Degree Vertices in
Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every

Class 1 conditions depending on the mini
Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree
✍ Thomas Niessen; Lutz Volkmann 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 694 KB

## Abstract A graph is called Class 1 if the chromatic index equals the maximum degree. We prove sufficient conditions for simple graphs to be Class 1. Using these conditions we improve results on some edge‐coloring theorems of Chetwynd and Hilton. We also improve a theorem concerning the 1‐factori

On numbers of vertices of maximum degree
On numbers of vertices of maximum degree in the spanning trees of a graph
✍ Jerzy Topp; Preben D. Vestergaard 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 611 KB

For a connected graph G, let ~-(G) be the set of all spanning trees of G and let nd(G) be the number of vertices of maximum degree in G. In this paper we show that if G is a cactus or a connected graph with p vertices and p+ 1 edges, then the set {na(T) : T C ~-(G)) has at most one gap, that is, it

A spanning tree of the 2m-dimensional hy
A spanning tree of the 2m-dimensional hypercube with maximum number of degree-preserving vertices
✍ Sul-young Choi; Puhua Guan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 190 KB

For an n-dimensional hypercube Q., the maximum number of degree-preserving vertices in a spanning tree is 2"jn if n = 2" for an integer M. (If n # 2", then the maximum number of degree-preserving vertices in a spanning tree is less than 2"/n.) We also construct a spanning tree of Qzm with maximum nu