Path eccentricity of graphs

Renzo Gómez, Juan Gutiérrez

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)


Let G be a connected graph. The eccentricity of a path P, denoted by eccG(P), is the maximum distance from P to any vertex in G. In the CENTRAL PATH (CP) problem, our aim is to find a path of minimum eccentricity. This problem was introduced by Cockayne et al., in 1981, in the study of different centrality measures on graphs. They showed that CP can be solved in linear time in trees, but it is known to be NP-hard in many classes of graphs such as chordal bipartite graphs, planar 3-connected graphs, split graphs, etc. We investigate the path eccentricity of a connected graph G as a parameter. Let pe(G) denote the value of eccG(P) for a central path P of G. We obtain tight upper bounds for pe(G) in some graph classes. We show that pe(G)≤1 on biconvex graphs and design an algorithm that finds such a path in linear time. On the other hand, by investigating the longest paths of a graph, we obtain tight upper bounds for pe(G) on arbitrary graphs and k-connected graphs. Finally, we study the relation between a central path and a longest path in a graph. We show that, on bipartite permutation graphs, a longest path is also a central path. Furthermore, for any such class of graphs, we exhibit a superclass that does not satisfy this property.

Idioma originalInglés
Páginas (desde-hasta)1-13
Número de páginas13
PublicaciónDiscrete Applied Mathematics
EstadoPublicada - 15 oct. 2023


Profundice en los temas de investigación de 'Path eccentricity of graphs'. En conjunto forman una huella única.

Citar esto