Article ID Journal Published Year Pages File Type
4647420 Discrete Mathematics 2014 6 Pages PDF
Abstract

For a fixed graph FF, a graph GG is FF-saturated   if there is no copy of FF in GG, but for any edge e∉Ge∉G, there is a copy of FF in G+eG+e. The minimum number of edges in an FF-saturated graph of order nn will be denoted by sat(n,F). A graph GG is weakly FF-saturated if GG contains no copy of FF and there is an ordering of the missing edges of GG so that if they are added one at a time, each edge added creates a new copy of FF. The minimum size of a weakly FF-saturated graph GG of order nn will be denoted by wsat(n,F). The graphs of order nn that are weakly FF-saturated will be denoted by wSAT(n,F), and those graphs in wSAT(n,F) with wsat(n,F) edges will be denoted by wSAT¯(n,F). The precise value of wsat(n,F) for many families of vertex disjoint copies of connected graphs such as small order graphs, trees, cycles, and complete graphs will be determined.

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