کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647420 | 1632406 | 2014 | 6 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 336, 6 December 2014, Pages 1–6