Computational and structural analysis of the contour of graphs

• Published date: 01 July 2018
• Author: Simone Dantas,Danilo Artigas,Thiago M. D. Silva,Alonso L. S. Oliveira
• Date: 01 July 2018
• DOI: http://doi.org/10.1111/itor.12290

Intl. Trans. in Op. Res. 25 (2018) 1315–1322

DOI: 10.1111/itor.12290

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Computational and structural analysis of the contour of graphs

Danilo Artigasa, Simone Dantasb,AlonsoL.S.Oliveira

aand Thiago M. D. Silvac

aInstituto de Ciˆ

encia e Tecnologia, UniversidadeFederal Fluminense, Rio das Ostras RJ, Brazil

bInstituto de Matem´

atica e Estat´

ıstica, Universidade FederalFluminense, Niter ´

oi RJ, Brazil

cInstituto de Matem´

atica, Pontif´

ıcia Universidade Cat´

olica do Rio de Janeiro, Rio de Janeiro RJ, Brazil

E-mail: daniloartigas@puro.uff.br [Artigas]; sdantas@im.uff.br[Dantas]; alonsoleonardo@id.uff.br [Oliveira];

thiagoomenez@mat.puc-rio.br [Silva]

Received 21 May2015; received in revised form 22 February 2016; accepted 3 March 2016

Abstract

Let G=(V,E)be a finite, simple, and connected graph. The closed interval I[S]ofasetS⊆Vis the set of

all vertices lying on a shortest path between any pair of vertices of S. The set Sis geodetic if I[S]=V.The

eccentricity of a vertex vis the number of edges in the greatest shortest path between vand any vertex wof

G.Avertexvis a contour vertex if no neighbor of vhas eccentricity greater than v. The contour Ct(G)of

Gis 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 forwhich 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.

Keywords:bipartite graphs; contour; convexity; geodetic set

1. Introduction

In the last few years many papers have been published extending the concept of convexity for

graph theory. These concepts were investigated under different aspects and have some interesting

applications like disease dissemination and virus propagation (Dourado et al., 2012). We consider

the so-called “geodesic convexity.” This subject has been studied in different contexts, such as

convex partitions (Artigas et al., 2011), geodetic sets (C´

aceres et al., 2006, 2008; Hernando et al.,

2013; Mezzini and Moscarini, 2015), geodetic number (Eroh and Oellermann, 2008), and hull

number (Dourado et al., 2009). In this work, we consider the problem (a)of deciding whether the

contour of a graph is geodetic, as proposed by C ´

aceres et al. (2005).

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.