𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On induced subgraphs of a block

✍ Scribed by Ladislav Nebeský

Publisher
John Wiley and Sons
Year
1977
Tongue
English
Weight
271 KB
Volume
1
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

If G is a block, then a vertex u of G is called critical if Gu is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices ul, u,, u2, and u2 of degree two in G such that ulul and u2uz are edges of G, and uIu2, u,uz, u1u2. and uluz are edges of the complement of G, and B) the 'complement of G is a block with no critical vertex of degree two.

📜 SIMILAR VOLUMES

Induced subgraphs of prescribed size
Induced subgraphs of prescribed size
✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A subgraph of a graph __G__ is called __trivial__ if it is either a clique or an independent set. Let __q(G)__ denote the maximum number of vertices in a trivial subgraph of __G__. Motivated by an open problem of Erdős and McKay we show that every graph __G__ on __n__ vertices for which

A result on Hamiltonian line graphs invo
A result on Hamiltonian line graphs involving restrictions on induced subgraphs
✍ H. J. Veldman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. O

Finite Induced Graph Ramsey Theory: On P
Finite Induced Graph Ramsey Theory: On Partitions of Subgraphs
✍ D.S. Gunderson; V. Rodl; N.W. Sauer 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 425 KB

For given finite (unordered) graphs \(G\) and \(H\), we examine the existence of a Ramsey graph \(F\) for which the strong Ramsey arrow \(F \rightarrow(G)_{r}^{\prime \prime}\) holds. We concentrate on the situation when \(H\) is not a complete graph. The set of graphs \(G\) for which there exists a

Random Induced Subgraphs of Generalizedn
Random Induced Subgraphs of Generalizedn-Cubes
✍ Christian M. Reidys 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 312 KB

vertices are adjacent if they differ in exactly one coordinate. Random induced subgraphs, . with probability . The first theorem shows that for s c ln n rn there exists n n a unique largest component in ⌫ -Q Q n which contains almost all vertices and that n ␣ Ž . the size of the second largest comp

Forbidden induced subgraph characterizat
Forbidden induced subgraph characterization of cograph contractions
✍ Igor Ed. Zverovich; Inessa I. Zverovich 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

Let S 1 ; S 2 ; . . . ; S t be pairwise disjoint non-empty stable sets in a graph H. The graph H Ã is obtained from H by: (i) replacing each S i by a new vertex q i ; (ii) joining each q i and q j , 1 i 6 ¼ j t, and; (iii) joining q i to all vertices in HÀ(S 1 [ S 2 [ Á Á Á [ S t ) which were adjace

A semi-induced subgraph characterization
A semi-induced subgraph characterization of upper domination perfect graphs
✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl