Skip to main content
Article
Proper Connection of Graphs
Discrete Mathematics
  • Valentin Borozan, University Paris
  • Shinya Fujita, Maebashi Institute of Technology
  • Aydin Gerek, Lehigh University
  • Colton Magnant, Georgia Southern University
  • Yannis Manoussakis, University Paris
  • Leandro Montero, University Paris
  • Zsolt Tuza, University of Pannonia
Document Type
Article
Publication Date
9-6-2012
DOI
10.1016/j.disc.2011.09.003
Disciplines
Abstract

An edge-colored graph G is k-proper connected if every pair of vertices is connected by k internally pairwise vertex-disjoint proper colored paths. The k-proper connection number of a connected graph G, denoted by pck(G), is the smallest number of colors that are needed to color the edges of G in order to make it k-proper connected. In this paper we prove several upper bounds for pck(G). We state some conjectures for general and bipartite graphs, and we prove them for the case when k=1. In particular, we prove a variety of conditions on G which imply pc1(G)=2.

Citation Information
Valentin Borozan, Shinya Fujita, Aydin Gerek, Colton Magnant, et al.. "Proper Connection of Graphs" Discrete Mathematics Vol. 312 Iss. 17 (2012) p. 2550 - 2560
Available at: http://works.bepress.com/colton_magnant/16/