Distance defined by spanning trees in graphs

Gary Chartrand, Ladislav Nebeský, and Ping Zhang. "Distance defined by spanning trees in graphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 485-506. <http://eudml.org/doc/270605>.

@article{GaryChartrand2007,
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ₖ = 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.},
author = {Gary Chartrand, Ladislav Nebeský, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance; geodesic; T-path; T-geodesic; T-distance; -path; -geodesic; -distance},
language = {eng},
number = {3},
pages = {485-506},
title = {Distance defined by spanning trees in graphs},
url = {http://eudml.org/doc/270605},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Gary Chartrand
AU - Ladislav Nebeský
AU - Ping Zhang
TI - Distance defined by spanning trees in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 485
EP - 506
AB - 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.
LA - eng
KW - distance; geodesic; T-path; T-geodesic; T-distance; -path; -geodesic; -distance
UR - http://eudml.org/doc/270605
ER -