A graph G is said to be degree preservable if for any spanning tree T of G, there exists a vertex v whose degree in T is equal to its degree in G. In this paper, we introduce the notion of vertex degree preservability of a graph G as the least number of edges that should be removed from G in order to get a graph G' which is degree preservable. We compute the vertex degree preservability for some of the most common families of graphs such as: bipartite and complete graphs.
|Number of pages||5|
|Journal||International Journal of Pure and Applied Mathematics|
|Publication status||Published - Mar 11 2011|
- Degree preservable graphs
- Spanning tree
ASJC Scopus subject areas
- Applied Mathematics