PDF

Discussiones Mathematicae Graph Theory 27(3) (2007) 485-506
DOI: https://doi.org/10.7151/dmgt.1375

DISTANCE DEFINED BY SPANNING TREES IN GRAPHS

Gary Chartrand Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA

Ladislav Nebeský Faculty of Philosophy  & Arts Charles University, Prague J. Palacha 2, CZ - 116 38 Praha 1, Czech Republic

Ping Zhang Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA

Abstract

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u−v path u = u₀, u₁, u₂, ☐, u_k = v in T. A u−v T-path in G is a u− v path u = v₀,v₁,☐,v_l = v in G that is a subsequence of the sequence u = u₀,u₁,u₂,☐ ,u_k = v. A u−v T-path of minimum length is a u− v T-geodesic in G. The T-distance d_{G| T}(u, v) from u to v in G is the length of a u−v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary and sufficient conditions are established for (1) geo(G) = geo(G|T) and (2) geo(G|T) = geo(G|T^*), where T and T^* are two spanning trees of G. It is shown for a connected graph G that geo(G|T) = geo(G) for every spanning tree T of G if and only if G is a block graph. For a spanning tree T of a connected graph G, it is also shown that geo(G|T) satisfies seven of the eight axioms of the characterization of geo(G). Furthermore, we study the relationship between the distance d and T-distance d_G|T in graphs and present several realization results on parameters and subgraphs defined by these two distances.

Keywords: distance, geodesic, T-path, T-geodesic, T-distance.

2000 Mathematics Subject Classification: 05C05, 05C12.

References

[1]	H. Bielak and M.M. Sysło, Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983) 269-75.
[2]	F. Buckley, Z. Miller and P.J. Slater, On graphs containing a given graph as center, J. Graph Theory 5 (1981) 427-434, doi: 10.1002/jgt.3190050413.
[3]	G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Boston, 2005).
[4]	F. Harary and R.Z. Norman, The dissimilarity characteristic of Husimi trees, Ann. of Math. 58 (1953) 134-141, doi: 10.2307/1969824.
[5]	L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994) 15-20.
[6]	L. Nebeský, A new proof of a characterization of the set of all geodesics in a connected graph, Czech. Math. J. 48 (1998) 809-813, doi: 10.1023/A:1022404126392.
[7]	L. Nebeský, The set of geodesics in a graph, Discrete Math. 235 (2001) 323-326, doi: 10.1016/S0012-365X(00)00285-5.

Received 6 July 2006
Revised 18 April 2007
Accepted 30 April 2007