𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Saturated graphs with minimal number of edges

✍ Scribed by L. Kászonyi; Zs. Tuza

Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
286 KB
Volume
10
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let F = {F,, . . .} be a given class of forbidden graphs. A graph G is called F-saturated if no F, E F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F-saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths, rn pairwise disjoint edges).

📜 SIMILAR VOLUMES

Numbers of edges in supermagic graphs
Numbers of edges in supermagic graphs
✍ Svetlana Drajnová; Jaroslav Ivančo; Andrea Semaničová 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we establish some bounds for the number of edges in sup

On the Number of Edges of Quadrilateral-
On the Number of Edges of Quadrilateral-Free Graphs
✍ Zoltán Füredi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 247 KB

If a graph has q 2 +q+1 vertices (q>13), e edges and no 4-cycles then e 1 2 q(q+1) 2 . Equality holds for graphs obtained from finite projective planes with polarities. This partly answers a question of Erdo s from the 1930's. 1996 Academic Press, Inc. ## 1. Results Let f (n) denote the maximum n

The Number of Removable Edges in 3-Conne
The Number of Removable Edges in 3-Connected Graphs
✍ Su Jianji 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

An edge of a 3-connected graph G is said to be removable if G&e is a subdivision of a 3-connected graph. Holton et al. (1990) proved that every 3-connected graph of order at least five has at least W(|G| +10)Â6X removable edges. In this paper, we prove that every 3-connected graph of order at least

Edge-face chromatic number and edge chro
Edge-face chromatic number and edge chromatic number of simple plane graphs
✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) →  {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_