共查询到20条相似文献,搜索用时 62 毫秒
1.
设 G是一个图,若对于 G的任意一边 G都有{P_2,Ci|i->3}-因子含有这条边,则称G是{P_2,Ci|i->3}-覆盖图.本文给出连通非二分图G是{P2,Ci|i->3}-覆盖图的充要条件为任给S■V(G),V(G)≠S≠■有i(G-S)_>|S|-1成立. 相似文献
2.
设F为有限序列族,对a=(a1,a2,…,an)∈F,ai为整数且0≤ai≤si(整数),记s(a)={j|1≤j≤n,aj>0},s(F)={s(a)|a∈F},及A{1,2,…,n}时W(A)=Пi∈Asi.称F为贪婪t-相交,如对任何a,b∈F,至少有t个ai,bi>0,且W(A)≥W(({1,2,…,n}-A)+B)对任何A∈S(F)及BA(|B|=t-1)成立.本文得到当s1>s2>…>sn时的最大贪婪t-相交有限序列族. 相似文献
3.
设G是无爪图.对x∈V(G),若G[N(x)]不连通,则存在yi∈V(G)-{x}(i-1,2),使|N(yi)∩Ki(x)|≥2,且|N(yi)∩N(Ki+1(x)){x}|≥2(i模2),那么称无爪图G是强2-阶邻域连通的,其中K1(x),K2(x)分别表示G[N(x)]的两个分支.本文证明了:连通且强2-阶邻域连通的无爪图是Hamilton图. 相似文献
4.
给一个图G,定义σ3(G)=min{Σ^3i=1d(vi)│{v1,v2,v3}}是G的无关集},p3(G)=min{│U^3i=1N(vi)‖{v1,v2,v3}是G中使│n^3i=1N(vi)│≠0}的无关集}。本文证明了:设G是n阶1-坚韧图,如果σ3(G)≥n,则G包含长度至少为min{n,2p3(G)+4}的圈,为个结果推广了若干已知结果,也解决了Broersma-Heuvel-Veld 相似文献
5.
复数域上线性系统x=A(t)x,当A(t)=(aij(t))n×n具有(n,N,r) 差异性质且rn时,解的特征数j有估计λj-limt→∞1t∫tt0Reaj(τ)dτn-1r+1-nlimt→∞1t∫tt0A(τ)dτ,j=1,2,…,n,其中A(t)=max{|aij(t)|:i,j=1,2,…,n,i≠j.} 相似文献
6.
星形函数族的一个子族的极值点与支撑点 总被引:1,自引:0,他引:1
设F({n})={f(z):f(z)在|z|<1内解析,f(z)=z-∞n=1anzn,an≥0,+∞n=2nan≤1},则F({n})是星形函数族的一个子族.许多学者研究了这个函数族.设M={f(z):f(z)在|z|<1内解析,f(z)=z-∞n=1anzn,an≥an+1≥0,+∞n=2nan≤1}.在本文中我们找出了函数族M的极值点与支撑点. 相似文献
7.
本文讨论了数学模型:max{f(x)│f(x)=min(1≤j≤n)〔c1jx1j+c2jx2j〕,x∈D},其中D={x│x={xij},nΣ(j=1)xij=a,i=1,2,xij≥0且为整数},并给出了一个拟多项式算法。 相似文献
8.
Dirac定理的局部化与Hamilton图 总被引:4,自引:0,他引:4
设G为一个n阶2-连通图,n≥3.若|Dn/2(K1,3)|≥2且满足下述条件之一:i)|Dn/2(K1,3+e)|≥2,ii)若K1,3+e→G,xy(?)E(K1,3+e),则max{dG(x),dG(y)}≥n/2,则G是一个Hamiltonian图或其闭包为sP|⊕H,这里sP⊕H是一类极小2-边连通图. 相似文献
9.
设G是一个图,若对于G的任意一边G都有{P2,Ci│i≥3}-因子含有这条边,则称G是{P2,Ci│i≥3}-覆盖图。本文给出连通非二分图G是{P2,Ci│i≥3}-覆盖图的充要条件为任给S包含于V(G),V(G)≠S≠ф有i(G-S)≤│S│-1成立。 相似文献
10.
11.
On graphs whose square have strong hamiltonian properties 总被引:1,自引:0,他引:1
The squareG2 of a graph G is the graph having the same vertex set as G and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if G has no cut-vertex, then G2 is Hamilton-connected (see [G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, C.St.J.A. Nash-Williams, The square of a block is hamiltonian connected, J. Combin. Theory Ser. B 16 (1974) 290-292; R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Combin. Theory Ser. B 20 (1976) 47-61]). We prove that if G has only one cut-vertex, then G2 is Hamilton-connected. In the case that G has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then G2 is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square. 相似文献
12.
A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we establish some bounds for the number of edges in supermagic graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 52: 15–26, 2006 相似文献
13.
The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v
1, v
2, ..., v
n
}, the extended double cover of G, denoted G
*, is the bipartite graph with bipartition (X, Y) where X = {x
1, x
2, ..., x
n
} and Y = {y
1, y
2, ..., y
n
}, in which x
i
and y
j
are adjacent iff i = j or v
i
and v
j
are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G
* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G
* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented. 相似文献
14.
For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then . 相似文献
15.
In this paper, a complete classification of arc-transitive cubic graphs of order 4p is given. 相似文献
16.
A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given. 相似文献
17.
设k≥2是一个整数。本文证明了任意有m条边的图都存在一个顶点的划分V_1,V_2…,V_k,使得e(V_1,V_2…,V_k)≥k-1/k m+k-1/2k((2m+1/4)~1/2-1/2)-(k-2)~2/8k,且max{e(V_i):1≤i≤k}≤m/k~2+(k-1)/2k~2((2m+1/4)~1/2-1/2+3/8-7k-4/8k~2.我们的结果改进了[Fan G.,Hou J.,Zeng Q.,A bound for judicious k-partitions of graphs,Discrete Appl.Math.,2014,179:86—99]的主要结论. 相似文献
18.
K. V. Kostousov 《Algebra and Logic》2008,47(2):118-124
We point out a countable set of pairwise nonisomorphic Cayley graphs of the group ℤ4 that are limit for finite minimal vertex-primitive graphs admitting a vertex-primitive automorphism group containing a regular
Abelian normal subgroup.
Supported by RFBR grant No. 06-01-00378.
__________
Translated from Algebra i Logika, Vol. 47, No. 2, pp. 203–214, March–April, 2008. 相似文献
19.
20.
We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained. 相似文献