1-join composition for $α$-critical graphs
| dc.creator | Valencia, Carlos E. | |
| dc.creator | Barrita, Marcos I. | |
| dc.date | 2007-07-27 | |
| dc.date | 2007-07-27 | |
| dc.date.accessioned | 2026-07-07T08:20:43Z | |
| dc.date.available | 2026-07-07T08:20:43Z | |
| dc.description | 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 $α$-critical} if $α(G\setminus e)> α(G)$ for all the edges e of G, where $α(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 $α$-critical graphs is important, for instance a complete description of $α$-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 $α$-critical graph. Therefore we get a very useful way to construct basic $α$-critical graphs using the 1-join of graphs. | |
| dc.description | 18 pages, 7 figures | |
| dc.identifier | https://arxiv.org/abs/0707.4085 | |
| dc.identifier | http://arxiv.org/abs/0707.4085 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/135148 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C75, 05C69 | |
| dc.title | 1-join composition for $α$-critical graphs | |
| dc.type | text |