Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: T-geodesic

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Distance defined by spanning trees in graphs

100%

Chartrand G., Nebeský L., Zhang P.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 3

485-506

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Chartrand G.

1 Nebeský L.

1 Zhang P.

1 2007

Wyniki wyszukiwania

Distance defined by spanning trees in graphs