✦ LIBER ✦

Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree

✍ Scribed by Thomas Niessen; Lutz Volkmann

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 694 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140211

No coin nor oath required. For personal study only.

✦ Synopsis

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‐factorization of regular graphs of high degree.

📜 SIMILAR VOLUMES

Degree sequence conditions for equal edg

Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique number

✍ Lutz Volkmann 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the

The number of cut-vertices in a graph of

The number of cut-vertices in a graph of given minimum degree

✍ Michael O. Albertson; David M. Berman 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 228 KB

Albertson, M.O. and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Mathematics 89 (1991) 97-100. A graph with n vertices and minimum degree k 2 2 can contain no more than (2k -2)n/(kz -2) cut-vertices. This bound is asymptotically tight. \* Research supported in

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

The irredundance number and maximum degr

The irredundance number and maximum degree of a graph

✍ B. Bollobás; E.J. Cockayne 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 104 KB

A vertex x in a subset X of vertices of an undirected graph is redundant if its dosed neighborhood is contained in the union of closed neighborhoods of vertices of X-{x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be irdorme

On the number of vertices of given degre

On the number of vertices of given degree in a random graph

✍ Zbigniew Palka 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor

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