Premium
An infinite class of reach‐preservable graphs
Author(s) -
Gagliardi Daniel,
Lewinter Marty
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199707)29:4<217::aid-net4>3.0.co;2-i
Subject(s) - combinatorics , spanning tree , bipartite graph , vertex (graph theory) , mathematics , minimum degree spanning tree , graph , minimum spanning tree , discrete mathematics
A vertex v of a spanning tree T of a graph G is called reach‐preserving if d G ( v , w ) = d T ( v , w ) for all w in G . G is called reach‐preservable if each of its spanning trees contains at least one reach‐preserving vertex. We show that K 2 , n is reach‐preservable. We show that a graph is bipartite if and only if given any pair of vertices, there exists a spanning tree in which both vertices a reach‐preserved. ® 1997 Wiley‐Liss, Inc.