# Distance defined by spanning trees in graphs

• Volume: 27, Issue: 3, page 485-506
• ISSN: 2083-5892

top

## Abstract

top
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}\left(u,v\right)$ 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.

## How to cite

top

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 -

## References

top
1. [1] H. Bielak and M.M. Sysło, Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983) 269-75. Zbl0569.05030
2. [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. Zbl0449.05056
3. [3] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Boston, 2005). Zbl1096.05001
4. [4] F. Harary and R.Z. Norman, The dissimilarity characteristic of Husimi trees, Ann. of Math. 58 (1953) 134-141, doi: 10.2307/1969824. Zbl0051.40502
5. [5] L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994) 15-20. Zbl0807.05045
6. [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. Zbl0949.05021
7. [7] L. Nebeský, The set of geodesics in a graph, Discrete Math. 235 (2001) 323-326, doi: 10.1016/S0012-365X(00)00285-5. Zbl1021.05031

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.