✦ LIBER ✦

Total matchings and total coverings of graphs

✍ Scribed by Y. Alavi; M. Behzad; L. M. Lesniak-Foster; E. A. Nordhaus

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 280 KB
Volume: 1
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190010209

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In graph theory, the related problems of deciding when a set of vertices or a set of edges constitutes a maximum matching or a minimum covering have been extensively studied. In this paper we generalize these ideas by defining total matchings and total coverings, and show that these sets, whose elements in general consist of both vertices and edges, provide a way to unify these concepts. Parameters denoting the maximum and the minimum cardinality of these sets are introduced and upper and lower bounds depending only on the order of the graph are obtained for the number of elements in arbitrary total matchings and total coverings. Precise values of all the parameters are found for several general classes of graphs, and these are used to establish the sharpness of most of the bounds. In addition, variations of some well known equalities due to Gallai relating covering and matching numbers are obtained.

📜 SIMILAR VOLUMES

Balloons, cut-edges, matchings, and tota

Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree

✍ Suil O; Douglas B. West 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 1 views

## Abstract A __balloon__ in a graph __G__ is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of __G__. Let __b__(__G__) be the number of balloons, let __c__(__G__) be the number of cut‐edges, and let α′(__G__) be the maximum size of a matching. Let \documentclass{article}\usep

On Generalizations of Matching-covered G

On Generalizations of Matching-covered Graphs

✍ Zoltán Szigeti 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Total weight choosability of graphs

✍ Tsai-Lien Wong; Xuding Zhu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

A graph G = (V , E) is called (k, k )-total weight choosable if the following holds: For any total list assignment L which assigns to each vertex x a set L(x) of k real numbers, and assigns to each edge e a set L(e) of k real numbers, there is a mapping f : V ∪E → R such that f (y) ∈ L(y) for any y

Cycle and cocycle coverings of graphs

✍ Sean McGuinness 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

In this article, we show that for any simple, bridgeless graph G on n vertices, there is a family C of at most n-1 cycles which cover the edges of G at least twice. A similar, dual result is also proven for cocycles namely: for any loopless graph G on n vertices and edges having cogirth g \* ≥ 3 and

On Total Colorings of Graphs

✍ C. Mcdiarmid; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 299 KB

AND Bruce Reed Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada

Total domination in graphs

✍ E. J. Cockayne; R. M. Dawes; S. T. Hedetniemi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB