Article ID Journal Published Year Pages File Type
4646914 Discrete Mathematics 2015 6 Pages PDF
Abstract

Let GG be a graph and SS be a set of non-negative integers. By an SS-degree free spanning forest of GG we mean a spanning forest of GG with no vertex degree in SS. In this paper we study the existence of {0,2}{0,2}-degree free spanning forests in graphs. We show that if GG is a graph with minimum degree at least 4, then there exists a {0,2}{0,2}-degree free spanning forest. Moreover, we show that every 2-connected graph with maximum degree at least 5 admits a {0,2}{0,2}-degree free spanning forest, and every 3-connected graph admits a {0,2}{0,2}-degree free spanning forest.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,