TY - JOUR

T1 - C4-saturated bipartite graphs

AU - Bryant, Darryn E.

AU - Fu, Hung-Lin

PY - 2002/12/28

Y1 - 2002/12/28

N2 - Let H be a graph. A graph G is said to be H-free if it contains no subgraph isomorphic to H. A graph G is said to be an H-saturated subgraph of a graph K if G is an H-free subgraph of K with the property that for any edge e∈E(K)\E(G), G ⊃ {e} is not H-free. We present some general results on Ks,t-saturated subgraphs of the complete bipartite graph Km,n and study the problem of finding, for all possible values of q, a C4-saturated subgraph of Km,n having precisely q edges.

AB - Let H be a graph. A graph G is said to be H-free if it contains no subgraph isomorphic to H. A graph G is said to be an H-saturated subgraph of a graph K if G is an H-free subgraph of K with the property that for any edge e∈E(K)\E(G), G ⊃ {e} is not H-free. We present some general results on Ks,t-saturated subgraphs of the complete bipartite graph Km,n and study the problem of finding, for all possible values of q, a C4-saturated subgraph of Km,n having precisely q edges.

UR - http://www.scopus.com/inward/record.url?scp=33845739424&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00371-0

DO - 10.1016/S0012-365X(02)00371-0

M3 - Article

AN - SCOPUS:33845739424

VL - 259

SP - 263

EP - 268

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -