On uniformly geodetic graphs

In this paper we study uniformly geodetic graphs. We shall give a diameter bound for these graphs. Further we characterize bipartite uniformly geodetic graphs and give some examples of them. In the last section we give two constructions and give sufficient conditions to assure that we get uniformly geodetic graphs from these constructions.     

Geodetic orientations of complete k-partite graphs

Ore defined a graph to be geodetic if and only if there is a unique shortest path between two points, and posed the problem of characterizing such graphs. Here this problem is studied in the context of oriented graphs and such geodetic orientations are characterized first for complete graphs (geodetic tournaments), then for complete bipartite and complete tripartite graphs, and finally for complete k-partite graphs.     

On the geodetic number of median graphs

A set of vertices S in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from S. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.     

Geodetic rays and fibers in periodic graphs

Using the notion of fibers, where two rays belong to the same fiber if and only if they lie within bounded Hausdorff‐distance of one another, we study how many fibers of a graph contain a geodetic ray and how many essentially distinct geodetic rays such “geodetic fibers” must contain. A complete answer is provided in the case of locally finite graphs that admit an almost transitive action by some infinite finitely generated, abelian group. Such graphs turn out to have either finitely many or uncountably many geodetic fibers. Furthermore, with finitely many possible exceptions, each of these fibers contains uncountably many geodetic rays. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 67–88, 2000     

Geodetic graphs of diameter two

We survey what is known on geodetic graphs of diameter two and discuss the implications of a new strong necessary condition for the existence of such graphs.     

Bigeodetic graphs

Bigeodetic graphs, a generalization of geodetic and interval-regular graphs, are defined as graphs in which each pair of vertices has at most two paths of minimum length between them. The block cut-vertex incidence pattern of bigeodetic separable graphs are discussed. Two characterizations of bigeodetic graphs are given and some properties of these graphs are studied. Construction of planar bigeodetic blocks with given girth and diameter, and construction of hamiltonian and eulerian/nonhamiltonian and noneulerian, perfect bigeodetic blocks are discussed. The extremal bigeodetic graph of diameterd onp d + 1 vertices is constructed.On leave from A.M. Jain College, Madras University, Madras 600114, India     

On metric properties of certain clique graphs

The paper provides a unified point of view on some classes of graphs: clique graphs, weakly geodetic graphs, ptolemaic graphs and Husimi trees. A purely metric characterization of Husimi trees is given.     

On F-geodetic graphs

We study the graphs in which the number of geodesics between any two vertices depends only on their distance. We consider also a connection between some of thesegraphs and geodetic graphs.     

On the geodetic number and related metric sets in Cartesian product graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in at least one interval between the vertices of S. The size of a minimum geodetic set in G is the geodetic number of G. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.     

Enumeration of labeled geodetic graphs with small cyclomatic number

Explicit expressions for the numbers of labeled geodetic bicyclic, tricyclic, and tetracyclic graphs with a given number of vertices are obtained.     

The lower and upper forcing geodetic numbers of block–cactus graphs

A vertex set D in graph G is called a geodetic set if all vertices of G are lying on some shortest u–v path of G, where u, v ∈ D. The geodetic number of a graph G is the minimum cardinality among all geodetic sets. A subset S of a geodetic set D is called a forcing subset of D if D is the unique geodetic set containing S. The forcing geodetic number of D is the minimum cardinality of a forcing subset of D, and the lower and the upper forcing geodetic numbers of a graph G are the minimum and the maximum forcing geodetic numbers, respectively, among all minimum geodetic sets of G. In this paper, we find out the lower and the upper forcing geodetic numbers of block–cactus graphs.     

New proof of a characterization of geodetic graphs

In [3], the present author used a binary operation as a tool for characterizing geodetic graphs. In this paper a new proof of the main result of the paper cited above is presented. The new proof is shorter and simpler.     

A note on geodetic graphs of diameter two and their relation to orthogonal Latin squares

A general class of matrices, which are equivalent to orthogonal Latin squares, is used to construct a class of geodetic graphs of diameter two. The argument is reversed to prove a necessary condition for the existence of general classes of such graphs in terms of orthogonal Latin squares.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

A characterization of ptolemaic graphs

A connected graph G is ptolemaic provided that for each four vertices U_i, 1 ≤ i ≤ 4, of G, the six distances d_ii = d_G (U_i, U_i), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P-Q and Q-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.