Independent spanning trees of chordal rings

Authors
Iwasaki, Y Kajiwara, Y Obokata, K Igarashi, Y
Citation
Y. Iwasaki et al., Independent spanning trees of chordal rings, INF PROCESS, 69(3), 1999, pp. 155-160
Citations number
12
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
69
Issue
3
Year of publication
1999
Pages
155 - 160
Database
ISI
SICI code
0020-0190(19990212)69:3<155:ISTOCR>2.0.ZU;2-I
Abstract
A chordal ring, denoted by CR(N, d), is a graph G = (V, E) with V = (0, 1, ..., N - 1) and E = ((u, v)\[v - u](N) = 1 or d), where 2 less than or equa l to N less than or equal to N/2 and [r](N) denotes r module N. We show tha t for 2 less than or equal to d less than or equal to N/2, CR(N, d) has fou r independent spanning trees rooted at the same vertex. (C) 1999 Elsevier S cience B.V. All rights reserved.