IJPAM: Volume 66, No. 2 (2011)

ON DEGREE PRESERVABLE GRAPHS

Nafaa Chbili
Department of Mathematical Science
College of Science
United Arab Emirates University
Al Ain, 17551, Abu Dhabi, UNITED ARAB EMIRATES
e-mail: nafaachbili@uaeu.ac.ae


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.

Received: October 9, 2010

AMS Subject Classification: 05C05

Key Words and Phrases: degree preservable graphs, spanning tree

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2011
Volume: 66
Issue: 2