Back to Search
Start Over
On subgraphs of Cartesian product graphs and S-primeness
- Source :
-
Discrete Mathematics . May2004, Vol. 282 Issue 1-3, p43. 10p. - Publication Year :
- 2004
-
Abstract
- In this paper we consider S-prime graphs, that is the graphs that cannot be represented as nontrivial subgraphs of nontrivial Cartesian products of graphs. Lamprey and Barnes characterized S-prime graphs via so-called basic S-prime graphs that form a subclass of all S-prime graphs. However, the structure of basic S-prime graphs was not known very well. In this paper we prove several characterizations of basic S-prime graphs. In particular, the structural characterization of basic S-prime graphs of connectivity <f>2</f> enables us to present several infinite families of basic S-prime graphs. Furthermore, simple S-prime graphs are introduced that form a relatively small subclass of basic S-prime graphs, and it is shown that every basic S-prime graph can be obtained from a simple S-prime graph by a sequence of certain transformations called extensions. [Copyright &y& Elsevier]
- Subjects :
- *GRAPHIC methods
*AGNATHA
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 282
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 12981534
- Full Text :
- https://doi.org/10.1016/j.disc.2003.11.005