Premium
On induced subgraphs of a block
Author(s) -
Nebeský Ladislav
Publication year - 1977
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190010113
Subject(s) - combinatorics , mathematics , vertex (graph theory) , block (permutation group theory) , complement (music) , degree (music) , discrete mathematics , graph , physics , chemistry , biochemistry , complementation , acoustics , gene , phenotype
If G is a block, then a vertex u of G is called critical if G ‐ u 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 u 2 , v 1 , u 2 , and v 2 of degree two in G such that u 1 v 1 and u 2 v 2 are edges of G , and u 1 v 2 , and u 2 v 2 are edges of the complement of G , and B) the complement of G is a block with no critical vertex of degree two.