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.
05C75 Structural characterization of families of graphs
Full Text: EuDML
[1] AKIYAMA J., HAMADA T., YOSHIMURA I.: Miscellaneous properties of middle graphs. TRU Math., 10, 1974, 41-53. · Zbl 0341.05125
[2] 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
[3] BEHZAD M., CHARTRAND G., LESNIAK-FOSTER I.: Graphs and Digraphs. Wadsworth, Belmont 1979. · Zbl 0403.05027
[4] BEINEKE L. W.: Characterizations of derived graphs. J. Comb. Theory, 9, 1970, 129-135. · Zbl 0202.55702
[5] BOSÁK J.: Geodetic graphs. Colloquia Math. Soc. J. Bolyai, 18, Keszthely, 1976, 151-172.
[6] BOSÁK J., KOTZIG A., ZNÁM Š.: Strongly geodetic graphs. J. Comb. Theory, 5, 1968, 170-176. · Zbl 0165.26602
[7] CVETKOVIĆ D. M., SIMIĆ S. K.: Graph equations for line graphs and total graphs. Discrete Math., 13, 1975, 315-320. · Zbl 0315.05126
[8] HAMADA T., YOSHIMURA I.: Traversability and connectivity of the middle graph of a graph. Discrete Math., 14, 1976, 247-255. · Zbl 0319.05122
[9] ORE O.: Theory of Graphs. Amer. Math. Soc. Colloq. Publ., 38, 1962. · Zbl 0105.35401
[10] PLESNÍK J.: Note on diametrically critical graphs. Recent Advances in Graph Theory. Academia, Prague 1975, 455-465. · Zbl 0326.05118
[11] 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.