Please use this identifier to cite or link to this item: http://hdl.handle.net/10077/4235
 Title: A Code for m-Bipartite Edge-Coloured Graphs Authors: Casali, Maria RitaGagliardi, 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 Mathematics32 suppl. 1 (2001) Abstract: An (n + 1)-coloured graph $\left(\Gamma,\gamma\right)$ is said tobe $m-bipartite$ if m is the maximum integer so that every m-residueof $\left(\Gamma,\gamma\right)$ (i.e. every connected subgraph whoseedges are coloured by only m colours) is bipartite; obviously, every(n + 1)-coloured graph, with n $\geq$ 2, results to be m-bipartitefor some m, with 2 $\leq$ m $\leq$ n + 1. In this paper, a numerical$code$ of length (2n \textminus{} m + 1) $\times$ q is assignedto each m-bipartite (n + 1)-coloured graph of order 2q. Then, it isproved 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 oneinto 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 theproblem of algorithmically recognizing H-isomorphic coloured graphsby means of a suitable defi{}nition of H-code. Type: Article URI: http://hdl.handle.net/10077/4235 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

CORE Recommender

#### Page view(s) 20

1,134
Last Week
9
Last month
checked on Jan 21, 2022