On Cartesian products of signed graphs (Q5896107): Difference between revisions

From MaRDI portal
Page on [mardi] deleted: Publication:5896107
Merged Item from Q5918775
description / endescription / en
 
scientific article; zbMATH DE number 7567779
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 / 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 / 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
Property / OpenAlex ID
 
Property / OpenAlex ID: W3159499939 / 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
links / mardi / namelinks / mardi / name
 

Revision as of 14:41, 29 April 2024

scientific article; zbMATH DE number 7567779
Language Label Description Also known as
English
On Cartesian products of signed graphs
scientific article; zbMATH DE number 7567779

    Statements

    On Cartesian products of signed graphs (English)
    0 references
    0 references
    21 July 2020
    0 references
    4 August 2022
    0 references
    prime factor decomposition of signed graphs
    0 references
    signed graphs
    0 references
    Cartesian products
    0 references
    prime factor decomposition
    0 references
    chromatic number
    0 references
    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.
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references