Premium
Embedding iterated line digraphs in books
Author(s) -
Hasunuma Toru
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10032
Subject(s) - digraph , iterated function , de bruijn sequence , combinatorics , embedding , line (geometry) , upper and lower bounds , mathematics , discrete mathematics , computer science , artificial intelligence , mathematical analysis , geometry
In this paper, we present an upper bound on the pagenumber of an iterated line digraph L k ( G ) of a digraph G . Our bound depends only on the digraph G and is independent of the number of iterations k . In particular, it is proved that the pagenumber of L k ( G ) does not increase with the number of iterations k . This result generalizes previous results on book‐embeddings of some particular families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, and butterfly networks. Also, we apply our result to wrapped butterfly networks. © 2002 Wiley Periodicals, Inc.