Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 171-175 |
| Number of pages | 5 |
| Journal | International Journal of Pure and Applied Mathematics |
| Volume | 66 |
| Issue number | 2 |
| Publication status | Published - 2011 |
Keywords
- Degree preservable graphs
- Spanning tree
ASJC Scopus subject areas
- General Mathematics
- Applied Mathematics