Diagonalized Cartesian products of S-prime graphs are S-prime

被引：3

作者：

Hellmuth, Marc ^{[1
,2
,3
]}

Ostermeier, Lydia ^{[1
,2
,3
]}

Stadler, Peter F. ^{[1
,2
,3
,4
,5
,6
]}

机构：

[1] Univ Leipzig, Dept Comp Sci, Bioinformat Grp, D-04107 Leipzig, Germany

[2] Univ Leipzig, Interdisciplinary Ctr Bioinformat, D-04107 Leipzig, Germany

[3] Max Planck Inst Math Sci, D-04103 Leipzig, Germany

[4] Fraunhofer Inst Zelltherapie & Immunol, D-04103 Leipzig, Germany

[5] Univ Vienna, Dept Theoret Chem, A-1090 Vienna, Austria

[6] Santa Fe Inst, Santa Fe, NM 87501 USA

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 01期

关键词：

S-prime; Diagonalized Cartesian product; Path-k-coloring; SUBGRAPHS;

D O I：

10.1016/j.disc.2011.03.033

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：74 / 80

页数：7

共 10 条

[1] On subgraphs of Cartesian product graphs and S-primeness [J].