Welcome To WUJNS
武汉大学学报 英文版 | Wuhan University Journal of Natural Sciences
Wan Fang
Wuhan University
Latest Article
Saturation Number for Linear Forest 2P3 ∪ tP2
LIU Min1, HU Zhiquan2
1. College of Economics, Northwest University of Political Science and Law, Xi’an 710063, Shaanxi, China; 2. School of Mathematics and Statistics, Central China Normal University, Wuhan 430079, Hubei, China
For a fixed graph F, a graph G is F-saturated if it has no F as a subgraph, but does contain F after the addition of any new edge. The saturation number, sat(n, F), is the minimum number of edges of a graph in the set of all F-saturated graphs with order n. In this paper, we determine the saturation number sat(n,2P3 ∪ tP2) and characterize the extremal graphs for n ⩾ 6t + 8.
Key words: saturation number; saturated graph; linear forest
CLC number:O 157.5
[1]	Bondy J A, Murty U S R. Graph Theory with Applica-tions[M]. New York: Elsevier, 1976.
[2]	Turan P. Eine extremalaufgabe aus der graphentheorie[J]. Mat Fiz Lapok, 1941, 48: 436-452.
[3]	Erdös P, Hajnal A, Moon J W. A problem in graph theory[J].  Am Math Mon, 1964, 71: 1107-1110.
[4]	Kászonyi L, Tuza Z. Saturated graphs with minimal number of edges[J]. J Graph Theory, 1986, 10: 203-210.
[5]	Bohman T, Fonoberova M, Pikhurko O. The saturation func-tion of complete partite graphs [J]. J Comb, 2010, 1: 149- 170.
[6]	Faudree J R, Ferrara M, Gould R J, et al. tKp-saturated graphs of minimum size [J]. Discret Math, 2009, 309(19): 5870-5876.
[7]	Faudree R J, Gould R J. Saturation numbers for nearly com-plete graphs[J]. Graphs Comb, 2013, 29: 429-448.
[8]	Bolloƀas B. On a conjecture of Erdos, Hajnal and Moon [J]. Am Math, 1967, 74: 178-179.
[9]	Chen Y. Minimum C5-saturated graphs [J]. J Graph Theory, 2009, 61(2): 111-126.
[10]	Chen Y. All minimum C5-saturated graphs [J]. J Graph Theory, 2011, 67(1): 9-26.
[11]	Tuza Z. C4-saturated graphs of minimum size[J]. Acta Univ  Carolin Math Phy, 1989, 30(2): 161-167. 
[12]	Zhang M, Luo S, Shigeno M. On the number of edges in a minimum C6-saturated graph[J]. Graphs Comb, 2015, 31: 1085-1106.
[13]	Chen G, Faudree R J, Gould R J. Saturation numbers of books[J]. Electron J Comb, 2008, 15(1): 118-129.
[14]	Faudree J R, Faudree R J, Gould R J, et al. Saturation num-bers for trees[J]. Electron J Comb, 2009, 16(1): 91-109.
[15]	Chen G, Faudree J R, Faudree R J, et al. Results and prob-lems on saturation numbers for linear forests[J]. Bull Inst Comb Appl, 2015, 75: 29-46.
[16]	Faudree J R, Faudree R J, Schmitt J R. A survey of minimum saturation graphs[J]. Electron J Comb, 2011,18: DS19.
[17]	Bushaw N, Kettle N. Turn of multiple of paths and equibi-partite forests[J]. Comb Probab Comput, 2011, 20: 837-853.
[18]	Berge C. Sur le couplage maximum d’un graph[J]. C R Acad Sci Paris, 1958, 247: 258-259.
Welcome To WUJNS

HOME | Aim and Scope | Editoral Board | Current Issue | Back Issue | Subscribe | Crosscheck | Polishing | Contact us Copyright © 1997-2020 All right reserved