𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dominating subgraphs in graphs with some forbidden structures

✍ Scribed by Jiping Liu; Huishan Zhou

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
387 KB
Volume
135
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We characterize the triangle-free graphs with neither induced path of six vertices nor induced cycle of six vertices and the triangle-free graphs without induced path of six vertices in terms of dominating subgraphs.

πŸ“œ SIMILAR VOLUMES

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ JΓ‘nos Pach; Micha Sharir πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent

Hamiltonicity and forbidden subgraphs in
Hamiltonicity and forbidden subgraphs in 4-connected graphs
✍ Florian Pfender πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 121 KB

## Abstract Let __T__ be the line graph of the unique tree __F__ on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., __T__ is a chain of three triangles. We show that every 4‐connected {__T__, __K__~1,3~}‐free graph has a hamiltonian cycle. Β© 2005 Wiley Periodicals, Inc. J Graph Theory 49:

r-Dominating cliques in graphs with hype
r-Dominating cliques in graphs with hypertree structure
✍ Feodor F. Dragan; Andreas BrandstΓ€dt πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 848 KB

Let G = (V, E) be an undirected graph and r be a vertex weight function with positive integer values. A subset (clique) D ~\_ V is an r-dominating set (clique) in G ifffor every vertex v e V there is a vertex u e D with dist(u, v) <~ r(v). This paper contains the following results: (i) We give a si