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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom