𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some arrowing results for trees versus complete graphs

✍ Scribed by Albert D. Polimeni; H. JosephS Straight; Jay Yellen

Book ID
118284384
Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
288 KB
Volume
5
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Some APX-completeness results for cubic
Some APX-completeness results for cubic graphs
✍ Paola Alimonti; Viggo Kann πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 122 KB

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded

Some results on tree decomposition of gr
Some results on tree decomposition of graphs
✍ Guoli Ding; Bogdan Oporowski πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 968 KB

## Abstract We investigate tree decompositions (__T__,(__X__~t~)~tΟ΅V(T)~) whose width is β€œclose to optimal” and such that all the subtrees of __T__ induced by the vertices of the graph are β€œsmall.” We prove the existence of such decompositions for various interpretations of β€œclose to optimal” and β€œ

Some results on Ξ»-valuation of graphs in
Some results on Ξ»-valuation of graphs involving complete bipartite graphs
✍ Sze-Chin Shee πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 389 KB

Shee, S.-C., Some results on I-valuation of graphs involving complete bipartite graphs, Discrete Mathematics 87 (1991) 73-80. In this paper we show that a graph G obtained from a complete bipartite graph K,,, and a collection of q (cmax{m, n}) stars G, by joining the centre of G, to every vertex of