The distinguishing number of the iterated line graph

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that for all simple graphs G other than the cycles C_3,C_4,C_5, and the claw K_1,3 there exists a K > 0 such that whenever k > K the k-th iterate of the line graph can be distinguished by at most two colors. Additionally we determine, for trees, when the distinguishing number of the line graph of T is greater than the distinguishing number of T.
10 pages, 2 figures

Keywords

Combinatorics, 05C15 (Primary) 05C75, 05C25 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/76331

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0509296
 http://arxiv.org/abs/math/0509296

Collections

arXiv