Name
Abstract | ||
|---|---|---|
A graph is said to be S-prime if, whenever it is a subgraph of a nontrivial Cartesian product graph, it is a subgraph of one of the factors. A diagonalized Cartesian product is obtained from a Cartesian product graph by connecting two vertices of maximal distance by an additional edge. We show there that a diagonalized product of S-prime graphs is again S-prime. Klavzar et al. [S. Klavzar, A. Lipovec, M. Petkovsek, On subgraphs of Cartesian product graphs, Discrete Math. 244 (2002) 223-230] proved that a graph is S-prime if and only if it admits a nontrivial path-k-coloring. We derive here a characterization of all path-k-colorings of Cartesian products of S-prime graphs. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2011.03.033 | Discrete Mathematics |
Keywords | DocType | Volume |
path- k -coloring,path-k-coloring,s-prime,s -prime,diagonalized cartesian product,s | Journal | 312 |
Issue | ISSN | Citations |
1 | Discrete Mathematics | 4 |
PageRank | References | Authors |
0.46 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| marc hellmuth | 1 | 148 | 22.80 |
| Lydia Ostermeier | 2 | 29 | 3.98 |
| Peter F. Stadler | 3 | 1839 | 152.96 |