Paper Info
Title
On the contour of bipartite graphs.
Abstract
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.
Year
DOI
Venue
2018
10.1016/j.dam.2016.10.017
Discrete Applied Mathematics
Keywords
Field
DocType
Bipartite graphs,Contour,Geodetic set,Convexity
Complete bipartite graph,Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Chordal graph,Bipartite graph,Cograph,Pathwidth,Mathematics,Maximal independent set
Journal
Volume
ISSN
Citations 
245
0166-218X
0
PageRank 
References 
Authors
0.34
13
2
Name
Order
Citations
PageRank
D. Artigas1112.45
R. Sritharan230523.52