Portal de Periódicos da CAPES

Some common properties for regularizable graphs, edge-critical graphs and b-graphs

1981; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-10704-5_10

1611-3349

Claude Berge,

Interconnection Networks and Systems

Publisher Summary This chapter presents an investigation on some relations between different classes of graphs: (1) the edge-critical graphs, (2) the well-covered graphs, where every maximal stable set is maximum, (3) the B-graphs, where each vertex is contained in some maximum stable set, (4) the regularizable graphs, and (5) the quasi-regularizable graphs. The chapter presents the mentioned graphs in full for the basic lemmas. The chapter also discusses the case of bipartite graphs. G ∉ g if G is edge-critical and has no connected component isomorphic to K 1 (isolated vertex) or K 2 (isolated edge). Every graph in Ң 2 is also in Ң 3 . Ң 4 is the class of all regularizable graphs, which have no bipartite connected components. If G is bipartite, then G ∉ Ң 1 , G ∉ Ң 2 , G ∉ Ң 3 , G ∉ Ң 4 . For a bipartite graph G = (X, Y; E ), the following properties are equivalent: (1) G is quasi-regularizable, (2) G has a perfect matching, (3) G is a B-graph, and (4) G is τ-vertex-critical.