The Cartesian product of graphs with loops

Tetiana Boiko; Johannes Cuno; Wilfried Imrich; Florian Lehner; Christiaan E. van de Woestijne

doi:10.26493/1855-3974.715.c3d

The Cartesian product of graphs with loops

Tetiana Boiko, Johannes Cuno, Wilfried Imrich, Florian Lehner, Christiaan E. van de Woestijne

Research output: Contribution to journal › Article › peer-review

Abstract

We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi–Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in O(m) time, where m is the number of edges of the given graph.

Original language	English
Pages (from-to)	1-9
Number of pages	9
Journal	Ars Mathematica Contemporanea
Volume	11
Issue number	1
DOIs	https://doi.org/10.26493/1855-3974.715.c3d
Publication status	Published - 2016

Access to Document

10.26493/1855-3974.715.c3dLicence: CC BY 4.0

Cite this

@article{ca88e54e35234760a1f9ae06a3a8f417,

title = "The Cartesian product of graphs with loops",

abstract = "We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi–Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in O(m) time, where m is the number of edges of the given graph.",

author = "Tetiana Boiko and Johannes Cuno and Wilfried Imrich and Florian Lehner and Woestijne, {Christiaan E. van de}",

year = "2016",

doi = "10.26493/1855-3974.715.c3d",

language = "English",

volume = "11",

pages = "1--9",

journal = "Ars Mathematica Contemporanea",

issn = "1855-3966",

publisher = "DMFA Slovenije",

number = "1",

}

TY - JOUR

T1 - The Cartesian product of graphs with loops

AU - Boiko, Tetiana

AU - Cuno, Johannes

AU - Imrich, Wilfried

AU - Lehner, Florian

AU - Woestijne, Christiaan E. van de

PY - 2016

Y1 - 2016

N2 - We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi–Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in O(m) time, where m is the number of edges of the given graph.

AB - We extend the definition of the Cartesian product to graphs with loops and show that the Sabidussi–Vizing unique factorization theorem for connected finite simple graphs still holds in this context for all connected finite graphs with at least one unlooped vertex. We also prove that this factorization can be computed in O(m) time, where m is the number of edges of the given graph.

U2 - 10.26493/1855-3974.715.c3d

DO - 10.26493/1855-3974.715.c3d

M3 - Article

SN - 1855-3966

VL - 11

SP - 1

EP - 9

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

IS - 1

ER -

The Cartesian product of graphs with loops

Abstract

Access to Document

Fingerprint

Cite this