首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 125 毫秒
1.
Let G be a simple graph with n vertices and m edges. Let λ1, λ2,…, λn, be the adjacency spectrum of G, and let μ1, μ2,…, μn be the Laplacian spectrum of G. The energy of G is E(G) = n∑i=1|λi|, while the Laplacian energy of G is defined as LE(G) = n∑i=1|μi-2m/n| Let γ1, γ2, ~ …, γn be the eigenvalues of Hermite matrix A. The energy of Hermite matrix as HE(A) = n∑i=1|γi-tr(A)/n| is defined and investigated in this paper. It is a natural generalization of E(G) and LE(G). Thus all properties about energy in unity can be handled by HE(A).  相似文献   

2.
An invariant σ2(G) of a graph is defined as follows: σ2(G) := min{d(u) + d(v)|u, v ∈V(G),uv ∈ E(G),u ≠ v} is the minimum degree sum of nonadjacent vertices (when G is a complete graph, we define σ2(G) = ∞). Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2(G) ≥ n + k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that |Ci| ≤ s and vi ∈ V(Ci) for all 1 ≤ i ≤ k.
The condition of degree sum σs(G) ≥ n + k - 1 is sharp.  相似文献   

3.
In this paper, we prove that if any set of |E(G)|- |V(G)| + 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn't form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.  相似文献   

4.
§1 IntroductionLet Pn,Cn,and Kn be the path,the cycle,and the complete graph of order n,respectively.The complete bipartite graph with cardinalities ofparts m and n is denoted byKm,n.Disjoint union of n copies of a graph G is denoted by n G;Gis the complement of agraph G.A setof pairwise non-adjacent vertices in a graph is called stable.A maximum stableset of a graph G has the largest cardinalityα( G) among all stable sets of G;α( G) is calledthe stability number of G.Let Z be a s…  相似文献   

5.
A tricyclic graph G =(V(G), E(G)) is a connected and simple graph such that|E(G)| = |V(G)|+2. Let Tg nbe the set of all tricyclic graphs on n vertices with girth g. In this paper, we will show that there exists the unique graph which has the largest signless Laplacian spectral radius among all tricyclic graphs with girth g containing exactly three(resp., four)cycles. And at the same time, we also give an upper bound of the signless Laplacian spectral radius and the extremal graph having the largest signless Laplacian spectral radius in Tg n,where g is even.  相似文献   

6.
A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L : V(G) → {1,2 ,n}, where n = |V(G)|. An increasing nonconsecutive path in a labeled graph (G,L) is either a path (u1,u2 uk) (k ≥ 2) in G such that L(u,) + 2 ≤ L(ui+1) for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). A labeling L is optimal if the labeling L produces the largest d(G, L). In this paper, a method simpler than that in Zverovich (2004) to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.  相似文献   

7.
Let G = (V, E) be a connected graph. X belong to V(G) is a vertex set. X is a 3-restricted cut of G, if G- X is not connected and every component of G- X has at least three vertices. The 3-restricted connectivity κ3(G) (in short κ3) of G is the cardinality of a minimum 3-restricted cut of G. X is called κ3-cut, if |X| = κ3. A graph G is κ3-connected, if a 3-restricted cut exists. Let G be a graph girth g ≥ 4, κ3(G) is min{d(x) + d(y) + d(z) - 4 : xyz is a 2-path of G}. It will be shown that κ3(G) = ξ3(G) under the condition of girth.  相似文献   

8.
For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let Undenote the set of all connected unicyclic graphs with order n, and Ur n= {G ∈ Un| d(x) = r for any vertex x ∈ V(Cl)}, where r ≥ 2 and Cl is the unique cycle in G. Every unicyclic graph in Ur nis said to be a cycle-r-regular graph.In this paper, we completely characterize that C39(2, 2, 2) ο Sn-8is the unique graph having minimal energy in U4 n. Moreover, the graph with minimal energy is uniquely determined in Ur nfor r = 3, 4.  相似文献   

9.
Abstract Let Kv be the complete graph on v vertices, and G a finite simple undirected graph without isolated vertices. A G-packing of Kv, denoted by (v, G, 1)-packing, is a pair (X,A) where X is the vertex set of K+ and +4 is a family of edge-disjoint subgraphs isomorphic to G in Kv. In this paper, the maximum number of subgraphs in a (v, G, 1)-packing is determined when G is K2 x K3, the Cartesian product of K2 and K3, leaving two orders undetermined. This design originated from the use of DNA library screening.  相似文献   

10.
The abe-conjecture for the ring of integers states that, for every ε 〉 0 and every triple of relatively prime nonzero integers (a, b, c) satisfying a + b = c, we have max(|a|, |b|, |c|) 〈 rad(abc)^1+ε with a finite number of exceptions. Here the radical rad(m) is the product of all distinct prime factors of m. In the present paper we propose an abe-conjecture for the field of all algebraic numbers. It is based on the definition of the radical (in Section 1) and of the height (in Section 2) of an algebraic number. From this abc-conjecture we deduce some versions of Fermat's last theorem for the field of all algebraic numbers, and we discuss from this point of view known results on solutions of Fermat's equation in fields of small degrees over Q.  相似文献   

11.
阶为$n$的图$G$的圈长分布是序列($c_1,c_2,\ldots,c_n$), 其中$c_i$是图$G$中长为$i$的圈数.本文得到如下结果: 设$A\subseteq E(K_{n,n+7})$,在以下情况, 图 $G$ 由其圈长分布唯一确定.(1) $G=K_{n,n+7}$(n\geq10)$;(2) $G=K_{n,n+7}-A$ $(|A|=1,n\geq12)$;(3)$G=K_{n,n+7}-A$(|A|=2,n\geq14)$;(4)$G=K_{n,n+7}-A$ $(|A|=3  相似文献   

12.
最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.  相似文献   

13.
Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.  相似文献   

14.
For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.  相似文献   

15.
A join graph denoted by G + H,is illustrated by connecting each vertex of graph G to each vertex of graph H.In this paper,we prove the crossing number of join product of K_5 + P_n is Z(5,n) + 2 n + [n/2] + 4 for n ≥ 2.  相似文献   

16.
在已有研究中,对于$p$-子群的正规化子而言,它的$p$-幂零性质对有限$p$-幂零群的结构具有重要的影响. 本文中, 设$P$是群$G$的西罗$p$-子群, $1\leq p^d<|P|$, 对于$P$的每个阶为$p^d$的正规子群$H$H,将$N_G(H)$的$p$-幂零性质减弱为$p$-超可解性质,结合$H$的弱$M$-可补充性质,探究$p$-超可解群的结构.同时,在$N_G(P)$是$p$-幂零的条件下,利用子群$K$的弱$M$-可补充条件研究群的$p$-幂零性质,其中$K_p\leq K$且$P''\leq K_p\leq \Phi(P)$. $K_p$是$K$的西罗$p$-子群.在一定程度上,主要结果推广了Frobenius定理.  相似文献   

17.
设$h(G; x) =h(G)$和$[G]_h$分别表示图$G$的伴随多项式和伴随等价类. 文中给出了$[G]_h$的一个新应用. 利用$[G]_h$, 给出了图$H{\;}(H \cong G)$伴随唯一的充要条件, 其中$H=(\bigcup_{i{\in}A}P_i){\bigcup}(\bigcup_{j{\in}B}U_j)$, $A \subseteq A^{'}=\{1,2,3,5\} \bigcup \{2n|n \in N, n \geq 3\}$, $B \subseteq B^{'}  相似文献   

18.
设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号