共查询到20条相似文献,搜索用时 15 毫秒
1.
LiuYan YuanJinjiang WangShiying 《高校应用数学学报(英文版)》2000,15(1):1-6
Abstract. A simple graph G is induced matching extendable,shortly IM-extendable,if every in-duced matching of G is included in a perfect matching of G. The degree conditions of IM-extend-able graphs are researched in this paper. The main results are as follows: 相似文献
2.
A graph G is a {d, d+k}-graph, if one vertex has degree d+k and the remaining vertices of G have degree d. In the special case of k = 0, the graph G is d-regular. Let k, p ⩾ 0 and d, n ⩾ 1 be integers such that n and p are of the same parity. If G is a connected {d, d+k{-graph of order n without a matching M of size 2|M| = n − p, then we show in this paper the following: If d = 2, then k ⩾ 2(p + 2) and
If d ⩾ 3 is odd and t an integer with 1 ⩽ t ⩽ p + 2, then
If d ⩾ 4 is even, then
The special case k = p = 0 of this result was done by Wallis [6] in 1981, and the case p = 0 was proved by Caccetta and Mardiyono [2] in 1994. Examples show that the given bounds (i)–(viii) are best possible. 相似文献
(i) | n ⩾ k + p + 6. |
(ii) | n ⩾ d + k + 1 for k ⩾ d(p + 2) |
(iii) | n ⩾ d(p + 3) + 2t + 1 for d(p + 2 −t) + t ⩽ k ⩽ d(p + 3 −t) + t − 3 |
(iv) | n ⩾ d(p + 3) + 2p + 7 for k ⩽ p. |
(v) | n ⩾ d + k + 2 − η for k ⩾ d(p + 3) + p + 4 + η |
(vi) | n ⩾ d + k + p + 2 − 2t = d(p + 4) + p + 6 for k = d(p + 3) + 4 + 2t and p ⩾ 1 |
(vii) | n ⩾ d + k + p + 4 for d(p + 2) ⩽ k ⩽ d(p + 3) + 2 |
(viii) | n ⩾ d(p + 3) + p + 4 for k ⩽ d(p + 2) − 2, where 0 ⩽ t ⩽ 1/2p − 1 and η = 0 for even p and 0 ⩽ t ⩽ 1/2(p − 1) and η = 1 for odd p. |
3.
Lutz Volkmann 《Czechoslovak Mathematical Journal》2010,60(1):77-83
Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ
k
(G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
$
\gamma _{k + 1} (G) \leqslant \frac{{|V(G)| + \gamma _k (G)}}
{2}.
相似文献
4.
Karl Robinson 《Aequationes Mathematicae》1981,22(1):302-306
It is shown that, for eachn 2 and k 3, there exist at least 2
n
-3 non-isomorphic loops of order 2
n
k which are Bol but not Moufang. In most cases this bound can be improved. 相似文献
5.
Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d
k
(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d
k
(G). For a fixed positive integer d, some conditions to insure d
k
(G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d
k
(G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.
Supported by NNSF of China (19971086). 相似文献
6.
For κ ⩾ 0 and r0 > 0 let ℳ(n, κ, r0) be the set of all connected, compact n-dimensional Riemannian manifolds (Mn, g) with Ricci (M, g) ⩾ −(n−1) κ g and Inj (M) ⩾ r0. We study the relation between the kth eigenvalue λk(M) of the Laplacian associated to (Mn,g), Δ = −div(grad), and the kth eigenvalue λk(X) of a combinatorial Laplacian associated to a discretization X of M. We show that there exist constants c, C > 0 (depending only on n, κ and r0) such that for all M ∈ ℳ(n, κ, r0) and X a discretization of
for all k < |X|. Then, we obtain the same kind of result for two compact manifolds M and N ∈ ℳ(n, κ, r0) such that the Gromov–Hausdorff distance between M and N is smaller than some η > 0. We show that there exist constants c, C > 0 depending on η, n, κ and r0 such that
for all
.
Mathematics Subject Classification (2000): 58J50, 53C20
Supported by Swiss National Science Foundation, grant No. 20-101 469 相似文献
7.
1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(
8.
A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}
9.
CHANG Jianming & FANG Mingliang Department of Mathematics Changshu Institute of Technology Changshu China Department of Applied Mathematics South China Agricultural University Guangzhou China 《中国科学A辑(英文版)》2006,49(9):1165-1174
Let R(z) be a rational function of degree d≥2. Then R(z) has at least one repelling periodic point of given period k≥2, unless k = 4 and d = 2, or k = 3 and d≤3, or k = 2 and d≤8. Examples show that all exceptional cases occur. 相似文献
10.
Mieczys?aw Borowiecki Piotr Borowiecki El?bieta Sidorowicz Zdzis?aw Skupień 《Czechoslovak Mathematical Journal》2010,60(2):571-587
A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number
of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n
2), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n. 相似文献
11.
On Approximate Geometric k -Clustering 总被引:1,自引:0,他引:1
J. Matoušek 《Discrete and Computational Geometry》2000,24(1):61-84
For a partition of an n -point set into k subsets (clusters) S
1
,S
2
,. . .,S
k
, we consider the cost function , where c(S
i
) denotes the center of gravity of S
i
. For k=2 and for any fixed d and ε >0 , we present a deterministic algorithm that finds a 2-clustering with cost no worse than (1+ε) -times the minimum cost in time O(n log n); the constant of proportionality depends polynomially on ε . For an arbitrary fixed k , we get an O(n log
k
n) algorithm for a fixed ε , again with a polynomial dependence on ε .
Received October 19, 1999, and in revised form January 19, 2000. 相似文献
12.
Zhi-quanHu FengTian 《应用数学学报(英文版)》2003,19(1):97-106
A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G)≥3κ-1/2 or δ(G)≥5κ-4.Several known results are generalized. 相似文献
13.
Wei Cao 《Czechoslovak Mathematical Journal》2007,57(1):253-268
A set S={x
1,...,x
n
} of n distinct positive integers is said to be gcd-closed if (x
i
, x
j
) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x
i
, x
j
]
t
) defined on any gcd-closed set S={x
1,...,x
n
} is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x
1,...,x
n
} such that the power LCM matrix ([x
i
, x
j
]
t
) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed
set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2. 相似文献
14.
Carsten Thomassen 《Journal of Graph Theory》1983,7(2):261-271
The existence of a function α(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least α(k) has a decomposition A ∪ B ∪ C such that G(A) has minimum degree at least k, each vertex of A is joined to at least k vertices of B, and no two vertices of B are separated by fewer than k vertices in G(G ∪ C). This is applied to prove the existence of subdivisions of complete bipartite graphs (complete graphs) with prescribed path lengths modulo k in graphs of sufficiently high minimum degree (chromatic number) and path systems with prescribed ends and prescribed lengths modulo k in graphs of sufficiently high connectivity. 相似文献
15.
Jiong Sheng LI Jian Hua YIN 《数学学报(英文版)》2006,22(4):1133-1138
Let σ(k, n) be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ(k, n) can be realized by a graph containing a clique of k + 1 vertices. Erdos et al. (Graph Theory, 1991, 439-449) conjectured that σ(k, n) = (k - 1)(2n- k) + 2. Li et al. (Science in China, 1998, 510-520) proved that the conjecture is true for k 〉 5 and n ≥ (k2) + 3, and raised the problem of determining the smallest integer N(k) such that the conjecture holds for n ≥ N(k). They also determined the values of N(k) for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N(k) ≤ (k2) + 3 for k ≥ 8. In this paper, we determine the exact values of σ(k, n) for n ≥ 2k+3 and k ≥ 6. Therefore, the problem of determining σ(k, n) is completely solved. In addition, we prove as a corollary that N(k) -= [5k-1/2] for k ≥6. 相似文献
16.
Mark Pankov 《Journal of Algebraic Combinatorics》2011,33(4):555-570
Let V be an n-dimensional vector space (4≤n<∞) and let Gk(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ
k
(V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ
k
(V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ
k
(V) is an apartment of Gk(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ
k
(V), 1<k<n−1. 相似文献
17.
In this paper, we obtain the following result: Let k, n
1 and n
2 be three positive integers, and let G = (V
1,V
2;E) be a bipartite graph with |V1| = n
1 and |V
2| = n
2 such that n
1 ⩾ 2k + 1, n
2 ⩾ 2k + 1 and |n
1 − n
2| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V
1 and y ∈ V
2 with xy
$
\notin
$
\notin
E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph. 相似文献
18.
The following results are proved. In Theorem 1, it is stated that there exist both finitely presented and not finitely presented
2-generated nonfree groups which are k-free-like for any k ⩾ 2. In Theorem 2, it is claimed that every nonvirtually cyclic (resp., noncyclic and torsion-free) hyperbolic m-generated group is k-free-like for every k ⩾ m + 1 (resp., k ⩾ m). Finally, Theorem 3 asserts that there exists a 2-generated periodic group G which is k-free-like for every k ⩾ 3.
Supported by NSF (grant Nos. DMS 0455881 and DMS-0700811). (A. Yu. Olshanskii, M. V. Sapir)
Supported by RFBR project No. 08-01-00573. (A. Yu. Olshanskii)
Supported by BSF grant (USA–Israel). (M. V. Sapir)
Translated from Algebra i Logika, Vol. 48, No. 2, pp. 245–257, March–April, 2009. 相似文献
19.
In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}
20.
Jian Wang 《高校应用数学学报(英文版)》2008,23(3):345-350
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that (1) m ≤ kn, (2) n ≤ km, (3) km-n = kn-m ≡ 0 (mod (k^2- 1)) and (4) λ(km-n)(kn-m) ≡ 0 (mod k(k- 1)(k^2 - 1)(m + n)). 相似文献
|