Let G be a graph, u and v two vertices of G, and X a subset of V(G). A u-v geodesic is a path between u and v of minimum length. Ig(u,v) is the set of vertices that lie on any u-v geodesic and Ig(X) is the set ⋃u,v∈XIg(u,v). X is g-convex if Ig(X)=X. Analogously, Im(u,v) is the set of vertices that lie on any induced path between u and v and Im(X) is the set ⋃u,v∈XIm(u,v). X is m-convex if Im(X)=X. The g-convex hull [X]g of X is the smallest g-convex set containing X. Igh(X) equals Ig(X), if h=1, and equals I(Igh−1(X)), if h>1. The geodetic iteration number, gin(X), of X in G is the smallest h such that Igh(X)=Igh+1(X)=[X]g. The geodetic iteration number of G, denoted by gin(G), is defined as gin(G)=maxgin(X)|X⊆V(G). In this paper we provide an O(n3m) time algorithm (where n and m are the cardinalities of the vertex set and of the edge set of the graph, respectively) to compute the geodetic iteration number of a graph belonging to the class, say Γ, of graphs in which the families of g-convex sets and of m-convex sets coincide (i.e., every g-convex set is m-convex). Since Γ properly contains the class of distance-hereditary graphs, this result extends the result in Dourado et al. (2016). Furthermore, we provide an O(n2m) time algorithm to compute the geodetic iteration number of a bipartite distance-hereditary graph.
On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent / Moscarini, M.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - (2020). [10.1016/j.dam.2019.12.022]
On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent
Moscarini M.
2020
Abstract
Let G be a graph, u and v two vertices of G, and X a subset of V(G). A u-v geodesic is a path between u and v of minimum length. Ig(u,v) is the set of vertices that lie on any u-v geodesic and Ig(X) is the set ⋃u,v∈XIg(u,v). X is g-convex if Ig(X)=X. Analogously, Im(u,v) is the set of vertices that lie on any induced path between u and v and Im(X) is the set ⋃u,v∈XIm(u,v). X is m-convex if Im(X)=X. The g-convex hull [X]g of X is the smallest g-convex set containing X. Igh(X) equals Ig(X), if h=1, and equals I(Igh−1(X)), if h>1. The geodetic iteration number, gin(X), of X in G is the smallest h such that Igh(X)=Igh+1(X)=[X]g. The geodetic iteration number of G, denoted by gin(G), is defined as gin(G)=maxgin(X)|X⊆V(G). In this paper we provide an O(n3m) time algorithm (where n and m are the cardinalities of the vertex set and of the edge set of the graph, respectively) to compute the geodetic iteration number of a graph belonging to the class, say Γ, of graphs in which the families of g-convex sets and of m-convex sets coincide (i.e., every g-convex set is m-convex). Since Γ properly contains the class of distance-hereditary graphs, this result extends the result in Dourado et al. (2016). Furthermore, we provide an O(n2m) time algorithm to compute the geodetic iteration number of a bipartite distance-hereditary graph.File | Dimensione | Formato | |
---|---|---|---|
Moscarini_geodetic_2020.pdf
Open Access dal 12/01/2022
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
443.7 kB
Formato
Adobe PDF
|
443.7 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.