Rainbow Connections of Graphs
Rainbow connections are natural combinatorial measures that are used in applications to secure the transfer of classified information between agencies in communication networks. Rainbow Connections of Graphs covers this new and emerging topic in
- PDF / 2,033,281 Bytes
- 108 Pages / 439.36 x 666.15 pts Page_size
- 64 Downloads / 259 Views
For further volumes: http://www.springer.com/series/10030
Xueliang Li • Yuefang Sun
Rainbow Connections of Graphs
123
Xueliang Li Center for Combinatorics Nankai University Tianjin 300071, P.R. China [email protected]
Yuefang Sun Center for Combinatorics Nankai University Tianjin 300071, P.R. China [email protected]
ISSN 2191-8198 e-ISSN 2191-8201 ISBN 978-1-4614-3118-3 e-ISBN 978-1-4614-3119-0 DOI 10.1007/978-1-4614-3119-0 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2012932206 Mathematics Subject Classification (2010): 05C15, 05C40, 05C69, 05C75, 05C76, 05C80, 68M10, 68Q17, 68Q25, 68R10, 90B18, 90C27, 94C15 © Xueliang Li, Yuefang Sun 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
The concept of rainbow connection of a graph was first introduced by G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang in 2006. Let G be a nontrivial connected graph on which an edge-coloring c : E(G) → {1, 2, · · · , n}, n ∈ N, is defined, where adjacent edges may be colored the same. A path is rainbow if no two edges of it are colored the same. An edge-colored graph G is rainbow connected if every two distinct vertices are connected by a rainbow path. An edge-coloring under which G is rainbow connected is called a rainbow coloring. Clearly, if a graph is rainbow connected, it must be connected. Conversely, every connected graph has a trivial edge-coloring that makes it rainbow connected by coloring edges with distinct colors. Thus, we define the rainbow connection number of a connected graph G, denoted by rc(G), as the smallest number of colors that are needed in order to make G rainbow connected. A rainbow coloring using rc(G) colors is called a minimum rainbow coloring. Obviously, the rainbow connection number can be viewed as a new kind of chromatic index. The rainbow connection number is not only a natural combinatorial measure, but it also has applications to the secure transfer of classified information between agencies. In addition, the rainbow connection number can also be motivated by its interesting interpretation in the area of networking. Suppose that G represents a network (e.g., a cellular network). We wish to route messages between any two vertices in a pipeline, and require that each link on
Data Loading...
