# zbMATH — the first resource for mathematics

Geodetic line, middle and total graphs. (English) Zbl 0734.05071
A graph (finite and without loops or multiple edges) is geodetic if there is at most one shortest path between each pair of vertices. The author proves the Theorem: If G is a connected graph with at least one edge, then the line graph of G is geodetic if and only if G is a tree or an odd cycle. Similarly, the middle graph of a connected graph is geodetic if and only if G is a tree, while the total graph of a graph is geodetic if and only if every connected component of G has at most one edge. The author also defines weakly and strongly geodetic graphs and gives the theorems corresponding to those above.
##### MSC:
 05C75 Structural characterization of families of graphs
##### Keywords:
geodetic; line graph; middle graph; total graph
Full Text:
##### References:
  AKIYAMA J., HAMADA T., YOSHIMURA I.: Miscellaneous properties of middle graphs. TRU Math., 10, 1974, 41-53. · Zbl 0341.05125  AKIYAMA J., HAMADA T., YOSHIMURA I.: Graph equations for line graphs, total graphs and middle graphs. TRU Math., 12, 1976, 31-34. · Zbl 0402.05058  BEHZAD M., CHARTRAND G., LESNIAK-FOSTER I.: Graphs and Digraphs. Wadsworth, Belmont 1979. · Zbl 0403.05027  BEINEKE L. W.: Characterizations of derived graphs. J. Comb. Theory, 9, 1970, 129-135. · Zbl 0202.55702  BOSÁK J.: Geodetic graphs. Colloquia Math. Soc. J. Bolyai, 18, Keszthely, 1976, 151-172.  BOSÁK J., KOTZIG A., ZNÁM Š.: Strongly geodetic graphs. J. Comb. Theory, 5, 1968, 170-176. · Zbl 0165.26602  CVETKOVIĆ D. M., SIMIĆ S. K.: Graph equations for line graphs and total graphs. Discrete Math., 13, 1975, 315-320. · Zbl 0315.05126  HAMADA T., YOSHIMURA I.: Traversability and connectivity of the middle graph of a graph. Discrete Math., 14, 1976, 247-255. · Zbl 0319.05122  ORE O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ., 38, 1962. · Zbl 0105.35401  PLESNÍK J.: Note on diametrically critical graphs. Recent Advances in Graph Theory. Academia, Prague 1975, 455-465. · Zbl 0326.05118  PLESNÍK J.: A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs. J. Comb. Theory Ser. B36, 1984, 284-297. · Zbl 0527.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.