1,721,175 research outputs found
On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent
Full text linkLet 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
Computing a metric basis of a 2-connected bipartite distance-hereditary graph
No full textA vertex x of a connected graph G resolves two distinct vertices u and v in V(G) if the distance between u and x differs from the distance between v and x. A subset X of V(G) resolves two distinct vertices u and v in G if there exists a vertex x in X that resolves u and v; X is a metric generator of G if, for every pair of distinct vertices u and v of G, X resolves u and v and is a metric basis of G if X is a metric generator of G with minimum cardinality. The metric dimension of G is the cardinality of a metric basis of G. The problem of finding the metric dimension of an arbitrary graph is NP-hard. In this paper we show that the problem is solvable in polynomial time for the class of 2-connected bipartite distance-hereditary graphs by providing an algorithm that computes a metric basis of a 2-connected bipartite distance-hereditary graph in O(|V(G)|2|E(G)|) time
The effect of glucocorticoid therapy on the prevention of respiratory distres syndrome and the mortality rate in premature infants of women with hypertensive disease of pregnancy
No full text
Esplorazione funzionale biofisica e biochimica dell'unità fetoplacentare nelle gravide ipertese
No full text
- …
