论文标题
在签名图的笛卡尔产品上
On Cartesian products of signed graphs
论文作者
论文摘要
在本文中，我们研究了Germina，Hameed和Zaslavsky（2011）定义的签名图的笛卡尔产品。在这里，我们关注其代数性能，并查看某些笛卡尔产品的色数。我们的主要结果之一是签名图的主要因子分解的单一性。这导致我们提出了一种算法，以基于Imrich和Peterin（2018）的分解算法的分解算法计算线性时间分解。我们还研究了签名图的色数，即签名图的最小顺序，输入签名的图允许在该图形上允许签名路径的笛卡尔产物，符号完整图的笛卡尔产物的笛卡尔产物的笛卡尔产物，符号完整图和签名的cartesian signed Cycles的笛卡尔产物的笛卡尔产物的基础图。
In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n [] P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.
