共查询到20条相似文献,搜索用时 639 毫秒
1.
A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds. 相似文献
2.
Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D0(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q0(n) to be the minimum of D0(G) over all graphs G of order n.We prove that for all n we have
log*n−log*log*n−2≤q0(n)≤log*n+22,