𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Extremal Result for Subgraphs with Few Edges

✍ Scribed by S. Brandt

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
427 KB
Volume
64
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that whenever the edge number of a graph of order (n \geqslant 517) ensures that it contains every complete graph and every forest with at most (n) vertices and at most (m) edges, then the graph contains every graph with at most (n) vertices and (m) edges if (m<n). The required edge numbers for complete graphs and for forests are derived from Turan's Theorem and from an earlier result of the author. respectively. : 1995 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Extremal Digraph Results for Topological
Extremal Digraph Results for Topological Complete Subgraphs
✍ C. Jagger πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 143 KB

We determine, to within a constant factor, the maximum size of a digraph that does not contain a topological complete digraph DK p of order p. Let t 1 ( p) be defined for positive p by where D denotes a digraph. We show that 1 16 p 2 < t 1 ( p) ≀ 44 p 2 . We also obtain results for containing topol

An algebraic multigrid method for finite
An algebraic multigrid method for finite element discretizations with edge elements
✍ S. Reitzinger; J. SchΓΆberl πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 162 KB

## Abstract This paper presents an algebraic multigrid method for the efficient solution of the linear system arising from a finite element discretization of variational problems in __H__~0~(curl,Ξ©). The finite element spaces are generated by NΓ©dΓ©lec's edge elements. A coarsening technique is pres

An algorithm for construction of a k-con
An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter
✍ Ulrich Schumacher πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 470 KB

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will

Amortization Results for Chromatic Searc
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues
✍ Joan Boyar; Rolf Fagerberg; Kim S Larsen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 396 KB

The intention in designing data structures with relaxed balance, such as chromatic search trees, is to facilitate fast updating on shared-memory asynchronous parallel architectures. To obtain this, the updating and rebalancing have been uncoupled, so extensive locking in connection with updates is a

Hybrid STF–FDTD approach for EM scatteri
Hybrid STF–FDTD approach for EM scattering analysis with an extremely slow-decaying pulse incidence
✍ Yubo Yan; Debiao Ge; Yinchao Chen πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

In this paper, we present a hybrid scattering transfer ( ) ( ) function STF and finite-difference time-domain FDTD approach for the calculation of electromagnetic transient responses with the incidence of an extremely slow-decaying pulse, e.g., a double-exponential pulse. We ( ) first introduce a sc