Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size |
| |
Authors: | CA Barefoot |
| |
Institution: | Department of Mathematics & Statistics, University of New Mexico, Albuquerque, NM 87131, USA |
| |
Abstract: | At the 4th International Graph Theory Conference 1980, G. Chartrand posed the following problem: If a (connected) graph G contains spanning trees with m and n pendant vertices, respectively, with m < n, does G contain a spanning tree with k pendant vertices for every integer k, where m < k < n? Recently, S. Schuster showed that the answer is yes. Several variations of this interpolation theorem will be given including the following generalization: If a connected graph G contains connected spanning subgraphs of size r with m and n pendant vertices, respectively, with m < n, then G contains a connected spanning subgraph of size r with k pendant vertices for every integer k, where m < k < n. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|