On Graphs with Proper Connection Number 2

An edge-colored graph is properly connected if for every pair of vertices u and v there exists a properly colored uv-path (i.e. a uv-path in which no two consecutive edges have the same color). The proper connection number of a connected graph G, denoted pc(G), is the smallest number of colors neede...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jill Faudree, Leah Berman, Glenn Chappell, Chris Hartman, John Gimbel, Gordon Williams
Formato:	article
Lenguaje:	EN
Publicado:	Georgia Southern University 2021
Materias:	proper connection edge-coloring class 1 graphs Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/5564ffd186f04c75936316bb80f35082
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5564ffd186f04c75936316bb80f35082
record_format	dspace
spelling	oai:doaj.org-article:5564ffd186f04c75936316bb80f350822021-11-16T16:59:16ZOn Graphs with Proper Connection Number 22470-985910.20429/tag.2021.080202https://doaj.org/article/5564ffd186f04c75936316bb80f350822021-08-01T00:00:00Zhttps://digitalcommons.georgiasouthern.edu/tag/vol8/iss2/2https://doaj.org/toc/2470-9859An edge-colored graph is properly connected if for every pair of vertices u and v there exists a properly colored uv-path (i.e. a uv-path in which no two consecutive edges have the same color). The proper connection number of a connected graph G, denoted pc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is properly connected. An edge-colored graph is flexibly connected if for every pair of vertices u and v there exist two properly colored paths between them, say P and Q, such that the first edges of P and Q have different colors and the last edges of P and Q have different colors. The flexible connection number of a connected graph G, denoted fpc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is flexibly connected. In this paper, we demonstrate several methods for constructing graphs with pc(G) = 2 and fpc(G) = 2. We describe several families of graphs such that pc(G) ≥ 2 and we settle a conjecture from [BFG+12]. We prove that if G is connected and bipartite, then pc(G) = 2 is equivalent to being 2-edge-connected and fpc(G) = 2 is equivalent to the existence of a path through all cut-edges. Finally, it is proved that every connected, k-regular, Class 1 graph has flexible connection number 2.Jill FaudreeLeah BermanGlenn ChappellChris HartmanJohn GimbelGordon WilliamsGeorgia Southern Universityarticleproper connectionedge-coloringclass 1 graphsMathematicsQA1-939ENTheory and Applications of Graphs, Vol 8, Iss 2 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	proper connection edge-coloring class 1 graphs Mathematics QA1-939
spellingShingle	proper connection edge-coloring class 1 graphs Mathematics QA1-939 Jill Faudree Leah Berman Glenn Chappell Chris Hartman John Gimbel Gordon Williams On Graphs with Proper Connection Number 2
description	An edge-colored graph is properly connected if for every pair of vertices u and v there exists a properly colored uv-path (i.e. a uv-path in which no two consecutive edges have the same color). The proper connection number of a connected graph G, denoted pc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is properly connected. An edge-colored graph is flexibly connected if for every pair of vertices u and v there exist two properly colored paths between them, say P and Q, such that the first edges of P and Q have different colors and the last edges of P and Q have different colors. The flexible connection number of a connected graph G, denoted fpc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is flexibly connected. In this paper, we demonstrate several methods for constructing graphs with pc(G) = 2 and fpc(G) = 2. We describe several families of graphs such that pc(G) ≥ 2 and we settle a conjecture from [BFG+12]. We prove that if G is connected and bipartite, then pc(G) = 2 is equivalent to being 2-edge-connected and fpc(G) = 2 is equivalent to the existence of a path through all cut-edges. Finally, it is proved that every connected, k-regular, Class 1 graph has flexible connection number 2.
format	article
author	Jill Faudree Leah Berman Glenn Chappell Chris Hartman John Gimbel Gordon Williams
author_facet	Jill Faudree Leah Berman Glenn Chappell Chris Hartman John Gimbel Gordon Williams
author_sort	Jill Faudree
title	On Graphs with Proper Connection Number 2
title_short	On Graphs with Proper Connection Number 2
title_full	On Graphs with Proper Connection Number 2
title_fullStr	On Graphs with Proper Connection Number 2
title_full_unstemmed	On Graphs with Proper Connection Number 2
title_sort	on graphs with proper connection number 2
publisher	Georgia Southern University
publishDate	2021
url	https://doaj.org/article/5564ffd186f04c75936316bb80f35082
work_keys_str_mv	AT jillfaudree ongraphswithproperconnectionnumber2 AT leahberman ongraphswithproperconnectionnumber2 AT glennchappell ongraphswithproperconnectionnumber2 AT chrishartman ongraphswithproperconnectionnumber2 AT johngimbel ongraphswithproperconnectionnumber2 AT gordonwilliams ongraphswithproperconnectionnumber2
_version_	1718426301723836416

On Graphs with Proper Connection Number 2

Ejemplares similares