Please use this identifier to cite or link to this item:
Title: A Code for m-Bipartite Edge-Coloured Graphs
Authors: Casali, Maria Rita
Gagliardi, Carlo
Issue Date: 2001
Publisher: Università degli Studi di Trieste. Dipartimento di Scienze Matematiche
Source: Maria Rita Casali and Carlo Gagliardi, "A Code for m-Bipartite Edge-Coloured Graphs", in: Rendiconti dell’Istituto di Matematica dell’Università di Trieste. An International Journal of Mathematics, 32 (2001) suppl.1, pp. 55–76.
Series/Report no.: Rendiconti dell’Istituto di Matematica dell’Università di Trieste. An International Journal of Mathematics
32 suppl. 1 (2001)
An (n + 1)-coloured graph $\left(\Gamma,\gamma\right)$ is said to
be $m-bipartite$ if m is the maximum integer so that every m-residue
of $\left(\Gamma,\gamma\right)$ (i.e. every connected subgraph whose
edges are coloured by only m colours) is bipartite; obviously, every
(n + 1)-coloured graph, with n $\geq$ 2, results to be m-bipartite
for some m, with 2 $\leq$ m $\leq$ n + 1. In this paper, a numerical
$code$ of length (2n \textminus{} m + 1) $\times$ q is assigned
to each m-bipartite (n + 1)-coloured graph of order 2q. Then, it is
proved that$any\; two\; such\; graphs\; have\; the\; same\; code\; if\; and\; only\; if\; they\; are\; colour-isomorphic$,
i.e. if a graph isomorphism exists, which transforms the graphs one
into the other, up to permutation of the edge-colouring. More precisely,
if H is a given group of permutations on the colour set, we face the
problem of algorithmically recognizing H-isomorphic coloured graphs
by means of a suitable defi{}nition of H-code.
Type: Article
ISSN: 0049-4704
Appears in Collections:Rendiconti dell'Istituto di Matematica dell'Università di Trieste: an International Journal of Mathematics vol.32 (2001) s1

Files in This Item:
File Description SizeFormat
CasaliGagliardiRendMat32s.pdf218.95 kBAdobe PDFThumbnail
Show full item record

CORE Recommender

Page view(s) 20

Last Week
Last month
checked on Jan 21, 2022

Download(s) 20

checked on Jan 21, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.