𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound for the path number of a graph

✍ Scribed by Alan Donald

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
529 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The path number of a graph G, denoted p(G), is the minimum number of edge‐disjoint paths covering the edges of G. LovΓ‘sz has proved that if G has u odd vertices and g even vertices, then p(G) ≀ 1/2 u + g ‐ 1 ≀ n ‐ 1, where n is the total number of vertices of G. This paper clears up an error in LovΓ‘sz's proof of the above result and uses an extension of his construction to show that p(G) ≀ 1/2 u + [3/4__g__] ≀ [3/4__n__].

πŸ“œ SIMILAR VOLUMES

An upper bound for the harmonious chroma
An upper bound for the harmonious chromatic number of a graph
✍ Sin-Min Lee; John Mitchem πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 149 KB πŸ‘ 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound for the k-domination numb
An upper bound for the k-domination number of a graph
✍ E. J. Cockayne; B. Gamble; B. Shepherd πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 82 KB πŸ‘ 2 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).

On an upper bound for the harmonious chr
On an upper bound for the harmonious chromatic number of a graph
✍ Zhikang Lu πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 125 KB πŸ‘ 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

An upper bound for the total chromatic n
An upper bound for the total chromatic number of dense graphs
✍ H. R. Hind πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 340 KB πŸ‘ 1 views

## Abstract In this paper we consider those graphs that have maximum degree at least 1/__k__ times their order, where __k__ is a (small) positive integer. A result of Hajnal and SzemerΓ©di concerning equitable vertex‐colorings and an adaptation of the standard proof of Vizing's Theorem are used to s