Name
Abstract | ||
|---|---|---|
Let G=(V,E) be a finite, simple, and connected graph. The closed interval I[S] of a set SV is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if I[S]=V. The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour Ct(G) of G is the set formed by the contour vertices of G. We consider two problems: (a) the problem of determining whether the contour of a graph class is geodetic; (b) the problem of determining if there exists a graph such that I[Ct(G)] is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem (a) and show two infinite families such that Ct(G) is not geodetic. Using computational tools, we establish the minimum graphs for which Ct(G) is not geodetic; and show that all graphs with |V|<13, and all bipartite graphs with |V|<18, are such that I[Ct(G)] is geodetic. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1111/itor.12290 | INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH |
Keywords | Field | DocType |
bipartite graphs, contour, convexity, geodetic set | Discrete mathematics,Graph,Combinatorics,Convexity,Indifference graph,Bipartite graph,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
25 | 4 | 0969-6016 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| D. Artigas | 1 | 11 | 2.45 |
| Simone Dantas | 2 | 119 | 24.99 |
| Alonso L. S. Oliveira | 3 | 0 | 0.34 |
| Thiago M. D. Silva | 4 | 0 | 0.34 |