Idioma:

On the contour of bipartite graphs

Artigas, D. ; Sritharan, R.

Discrete Applied Mathematics, 2018-08, Vol.245, p.148-154 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
On the contour of bipartite graphs
Autor: Artigas, D. ; Sritharan, R.
Assuntos: Bipartite graphs ; Contour ; Contours ; Convexity ; Geodetic set ; Graph theory ; Graphs ; Mathematics ; Shape ; Shortest-path problems
É parte de: Discrete Applied Mathematics, 2018-08, Vol.245, p.148-154
Descrição: A vertex of a connected graph is a contour vertex provided the eccentricity of the vertex is at least as large as that of each of its neighbors. We consider the question of whether the set S of contour vertices of a connected graph is geodetic, i.e., whether every vertex of the graph lies on a shortest path (geodesic) between some pair of vertices in S. In general, it is known that when long induced cycles are forbidden (for chordal graphs) the answer is in the affirmative, but otherwise (even for weakly chordal graphs) the answer is in the negative. For bipartite graphs, it is known that when long induced cycles are allowed, the answer is in the negative. In contrast, we show that when long induced cycles are forbidden in bipartite graphs, namely for chordal bipartite graphs, the answer is in the affirmative. Our result also shows that while the answer is in the negative for bipartite graphs and weakly chordal graphs, for a graph that is both bipartite and weakly chordal, the answer is in the affirmative.
Editor: Amsterdam: Elsevier B.V
Idioma: Inglês

Voltar para lista de resultados