Mathematics – Combinatorics
Scientific paper
2007-07-27
Mathematics
Combinatorics
18 pages, 7 figures
Scientific paper
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(G\setminus e)> \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.
Barrita Marcos I.
Valencia Carlos E.
No associations
LandOfFree
1-join composition for $α$-critical graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with 1-join composition for $α$-critical graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 1-join composition for $α$-critical graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-271725