# Distance defined by spanning trees in graphs

Gary Chartrand; Ladislav Nebeský; Ping Zhang

Discussiones Mathematicae Graph Theory (2007)

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

## Access Full Article

top## Abstract

top## How to cite

topGary 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] H. Bielak and M.M. Sysło, Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983) 269-75. Zbl0569.05030
- [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] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Boston, 2005). Zbl1096.05001
- [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] L. Nebeský, A characterization of the set of all shortest paths in a connected graph, Math. Bohem. 119 (1994) 15-20. Zbl0807.05045
- [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] 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 ?

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