1-join composition for \alpha-critical graphs

arXiv0707.4085MaRDI QIDQ6206325FDOQ6206325

Marcos I. Barrita, Carlos Valencia

Publication date: 27 July 2007

Abstract: Given two graphs G and H its 1-{it join} is the graph obtained by taking the disjoint union of G and H and adding all the edges between a nonempty subset of vertices of G and a nonempty subset of vertices of H. In general, composition operations of graphs has played a fundamental role in some structural results of graph theory and in particular the 1-join composition has played an important role in decomposition theorems of several class of graphs such as the claw-free graphs, the bull-free graphs, the perfect graphs, etc. A graph G is called {it $alpha$-critical} if $alpha(Gsetminuse)>alpha(G)$ for all the edges e of G, where $alpha(G)$, the {it stability number} of G, is equal to the maximum cardinality of a stable set of G, and a set of vertices M of G is {it stable} if no two vertices in M are adjacent. The study $alpha$-critical graphs is important, for instance a complete description of $alpha$-critical graphs would yield a good characterization of the stability number of G. In this paper we give necessary and sufficient conditions that G and H must satisfy in order to its 1-join will be an $alpha$-critical graph. Therefore we get a very useful way to construct basic $alpha$-critical graphs using the 1-join of graphs.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

This page was built for publication: 1-join composition for $\alpha$-critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206325)