Geodesic
Distance defined by spanning trees in graphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 485-506

Voir la notice de l'article provenant de la source Library of Science

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ₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = 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 
@article{DMGT_2007_27_3_a6,
     author = {Chartrand, Gary and Nebesk\'y, Ladislav and Zhang, Ping},
     title = {Distance defined by spanning trees in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {485--506},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a6/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Nebeský, Ladislav
AU  - Zhang, Ping
TI  - Distance defined by spanning trees in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 485
EP  - 506
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a6/
LA  - en
ID  - DMGT_2007_27_3_a6
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Nebeský, Ladislav
%A Zhang, Ping
%T Distance defined by spanning trees in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 485-506
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a6/
%G en
%F DMGT_2007_27_3_a6
Chartrand, Gary; Nebeský, Ladislav; Zhang, Ping. Distance defined by spanning trees in graphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 485-506. http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a6/