๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Measuring the vulnerability for classes of intersection graphs

โœ Scribed by Dieter Kratsch; Ton Kloks; Haiko Muller

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
780 KB
Volume
77
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A general method for the computation of various parameters measuring the vulnerability of a graph is introduced. Four measures of vulnerability are considered, i.e., the toughness, scattering number, vertex integrity and the size of a minimum balanced separator. We show how to compute these parameters by polynomial-time algorithms for various classes of intersection graphs like permutation graphs, bounded dimensional cocomparability graphs, interval graphs, trapezoid graphs and circular versions of these graph classes.

๐Ÿ“œ SIMILAR VOLUMES

Characterizing intersection classes of g
Characterizing intersection classes of graphs
โœ Edward R. Scheinerman ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 571 KB

A graph is an intersection graph if it is possible to assign sets to its vertices so that adjacency corresponds exactly to nonempty intersection. If the sets assigned to vertices must belong to a pre-specified family, the resulting class of all possible intersection graphs is called an intersection

The intersection graph of random sets
The intersection graph of random sets
โœ Hiroshi Maehara ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 369 KB

Maehara, H., The intersection graph of random sets, Discrete Mathematics 87 (1991) 97-104. Let X,, i=l,..., n, be n = n(N) independent random subsets of {1,2,. . , N}, each selected at random out of the 2N subsets. We present some asymptotic (N-tm) properties of {Xi}, e.g. if r~/2~'~--+ m then {Xi}

Subdivision thresholds for two classes o
Subdivision thresholds for two classes of graphs
โœ C.A. Barefoot; L.H. Clark; A.J. Depew; R.C. Entringer; L.A. Szรฉkely ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 902 KB

The subdivision threshold for a graph F is the maximum number of edges, ex(n; FS), a graph of order n can have without containing a subdivision of F as a subgraph. We consider two instances: (i) F is the graph formed by a cycle C one vertex of which is adjacent to k vertices not on C, and (ii) F is

Genus distributions for two classes of g
Genus distributions for two classes of graphs
โœ Merrick L Furst; Jonathan L Gross; Richard Statman ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 663 KB