Item:Q5918775: Difference between revisions

From MaRDI portal
Item:Q5918775
Added link to MaRDI item.
Redirected to Q5896107
Tag: New redirect
 
(5 intermediate revisions by 4 users not shown)
redirectredirect
 
Q5896107
label / enlabel / en
On Cartesian products of signed graphs
description / endescription / en
scientific article; zbMATH DE number 7567779
Property / instance of
 
Property / instance of: scholarly article / rank
Normal rank
 
Property / title
On Cartesian products of signed graphs (English)
 
Property / title: On Cartesian products of signed graphs (English) / rank
Normal rank
 
Property / zbMATH Open document ID
 
Property / zbMATH Open document ID: 1494.05051 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/j.dam.2021.03.023 / rank
Normal rank
 
Property / author
 
Property / author: Dimitri Lajou / rank
Normal rank
 
Property / published in
 
Property / published in: Discrete Applied Mathematics / rank
Normal rank
 
Property / publication date
4 August 2022
Timestamp+2022-08-04T00:00:00Z
Timezone+00:00
CalendarGregorian
Precision1 day
Before0
After0
 
Property / publication date: 4 August 2022 / rank
Normal rank
 
Property / full work available at URL
 
Property / full work available at URL: https://arxiv.org/abs/2010.10066 / rank
Normal rank
 
Property / review text
The Cartesian product of signed graphs is defined by \textit{K. A. Germina} et al. [Linear Algebra Appl. 435, No. 10, 2432--2450 (2011; Zbl 1222.05223)]. Here, the authors focus on its algebraic properties and look at the chromatic number of some Cartesian products. The main result is the unicity of the prime factor decomposition of signed graphs. This leads the author to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by \textit{W. Imrich} and \textit{I. Peterin} [Discrete Math. 341, No. 5, 1336--1343 (2018; Zbl 1383.05271)]. 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 an underlying graph of the form \(P_n\square P_m\), of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles are studied. \textit{T. Zaslavsky} [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] gave a way to determine if two signed graphs are equivalent in linear time. Note that there is a difference between considering the chromatic number of the Cartesian product of two signed graphs and the chromatic number of a signed graph whose underlying graph is a Cartesian product. This is an interesting and nicely explained paper and useful to signed graph researchers.
 
Property / review text: The Cartesian product of signed graphs is defined by \textit{K. A. Germina} et al. [Linear Algebra Appl. 435, No. 10, 2432--2450 (2011; Zbl 1222.05223)]. Here, the authors focus on its algebraic properties and look at the chromatic number of some Cartesian products. The main result is the unicity of the prime factor decomposition of signed graphs. This leads the author to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by \textit{W. Imrich} and \textit{I. Peterin} [Discrete Math. 341, No. 5, 1336--1343 (2018; Zbl 1383.05271)]. 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 an underlying graph of the form \(P_n\square P_m\), of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles are studied. \textit{T. Zaslavsky} [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] gave a way to determine if two signed graphs are equivalent in linear time. Note that there is a difference between considering the chromatic number of the Cartesian product of two signed graphs and the chromatic number of a signed graph whose underlying graph is a Cartesian product. This is an interesting and nicely explained paper and useful to signed graph researchers. / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: V. Lokesha / rank
Normal rank
 
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C22 / rank
Normal rank
 
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C76 / rank
Normal rank
 
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C15 / rank
Normal rank
 
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 68R10 / rank
Normal rank
 
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 7567779 / rank
Normal rank
 
Property / zbMATH Keywords
signed graphs
 
Property / zbMATH Keywords: signed graphs / rank
Normal rank
 
Property / zbMATH Keywords
Cartesian products
 
Property / zbMATH Keywords: Cartesian products / rank
Normal rank
 
Property / zbMATH Keywords
prime factor decomposition
 
Property / zbMATH Keywords: prime factor decomposition / rank
Normal rank
 
Property / zbMATH Keywords
chromatic number
 
Property / zbMATH Keywords: chromatic number / rank
Normal rank
 
links / mardi / namelinks / mardi / name

Latest revision as of 14:41, 29 April 2024

Redirect to: