Mutiplicativity of oriented cycles
type: Item
instance of: scholarly article
title: Mutiplicativity of oriented cycles
zbMATH Open document ID: 0803.05029
author: Xuding Zhu
author: Pavol Hell
author: Huishan Zhou
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-01-02T00:00:00Z
review text: A homomorphism from a digraph \(G\) to a digraph \(H\) is a mapping \(f: V(G)\to V(H)\) such that \(gg'\in E(G)\) implies \(f(g)f(g')\in E(H)\); where such a homomorphism exists one writes \(G\to H\), otherwise \(G\not\to H\). The categorical product of digraphs \(G\) and \(H\), denoted by \(G\times H\), has vertex set \(V(G)\times V(H)\), and edge set \(\{(g,h)(g',h'): gg'\in E(G)\), \(hh'\in E(H)\}\). A digraph \(D\) is multiplicative if, for any digraphs \(G\), \(H\), \(G\times H\not\to D\) whenever both \(G\not\to D\) and \(H\not\to D\). The present paper continues a study begun by the second author [On the nonmultiplicativity of oriented cycles, SIAM J. Discrete Math. 5, No. 2, 207-218 (1992; Zbl 0773.05074)] concerned with a class of orientations of an \(n\)-cycle, here called \({\mathcal C}\)-cycles. ``In this paper, we shall\dots show\dots that all \({\mathcal C}\)-cycles are\dots multiplicative. Thus we achieve a classification of oriented cycles according to their being or not being multiplicative; this classification turns out to be surprisingly complex''.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 562406
zbMATH Keywords: multiplicativity
zbMATH Keywords: Hedetniemi conjecture
zbMATH Keywords: homomorphism
zbMATH Keywords: digraph
zbMATH Keywords: categorical product
zbMATH Keywords: oriented cycles
reviewed by: William G. Brown
MaRDI profile type: Publication
full work available at URL: jctb.1994.1016
OpenAlex ID: W1969953878
DOI: 10.1006/JCTB.1994.1016
Recommended article: Homomorphisms to oriented cycles
Recommended article: On the Nonmultiplicativity of Oriented Cycles
Recommended article: On multiplicative graphs and the product conjecture
Recommended article: Multiplicativity of acyclic digraphs
Recommended article: Optimal orientations of vertex-multiplications of cartesian products of graphs
Recommended article: Q4347899
Recommended article: Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
Recommended article: k-cyclic Orientations of Graphs
Recommended article: Decompositions of uniform complete directed multigraphs into each of the orientations of a 4-cycle
Recommended article: The Existence of Homomorphisms to Oriented Cycles
description: scientific article; zbMATH DE number 562406