首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 140 毫秒
1.
The chromatic polynomial of a simple graph G with n>0 vertices is a polynomial of degree n, where αk(G) is the number of k-independent partitions of G for all k. The adjoint polynomial of G is defined to be , where is the complement of G. We find explicit formulas for the adjoint polynomials of the bridge–path and bridge–cycle graphs. Consequence, we find the zeros of the adjoint polynomials of several families of graphs.  相似文献   

2.
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.  相似文献   

3.
The Randi? indexR(G) of a graph G is defined as the sum of over all edges uv of G, where du and dv are the degrees of vertices u and v, respectively. Let D(G) be the diameter of G when G is connected. Aouchiche et al. (2007) [1] conjectured that among all connected graphs G on n vertices the path Pn achieves the minimum values for both R(G)/D(G) and R(G)−D(G). We prove this conjecture completely. In fact, we prove a stronger theorem: If G is a connected graph, then , with equality if and only if G is a path with at least three vertices.  相似文献   

4.
The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in Rk. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Qd, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).  相似文献   

5.
A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .  相似文献   

6.
Two cycles are said to be adjacent if they share a common edge. Let G be a planar graph without triangles adjacent 4-cycles. We prove that if Δ(G)≥6, and and if Δ(G)≥8, where and denote the list edge chromatic number and list total chromatic number of G, respectively.  相似文献   

7.
Let G be a simple graph on n vertices and π(G)=(d1,d2,…,dn) be the degree sequence of G, where n≥3 and d1d2≤?≤dn. The classical Pósa’s theorem states that if dmm+1 for and dm+1m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that dmm+1 for and dm+1m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs.  相似文献   

8.
Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that Ac=[cij] is the conjugate adjacency matrix of the graph G if cij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and cij=0 if i=j. Let PG(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if PG(λ)=PH(λ) and . Further, let Pc(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs Gi=G?i(i=1,2,…,n). If Pc(G)=Pc(H) we prove that , provided that the order of G is greater than 2.  相似文献   

9.
A random n-lift of a base-graph G is its cover graph H on the vertices [nV(G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(i),v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.Let G be a graph with largest eigenvalue λ1 and let ρ be the spectral radius of its universal cover. Friedman (2003) [12] proved that every “new” eigenvalue of a random lift of G is with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995) [15]. Linial and Puder (2010) [17] improved Friedman?s bound to . For d-regular graphs, where λ1=d and , this translates to a bound of O(d2/3), compared to the conjectured .Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is . This result is tight up to a logarithmic factor, and for λ?d2/3−ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.  相似文献   

10.
Let G,G be finite abelian groups with nontrivial homomorphism group . Let Ψ be a non-empty subset of . Let DΨ(G) denote the minimal integer, such that any sequence over G of length DΨ(G) must contain a nontrivial subsequence s1,…,sr, such that for some ψiΨ. Let EΨ(G) denote the minimal integer such that any sequence over G of length EΨ(G) must contain a nontrivial subsequence of length |G|,s1,…,s|G|, such that for some ψiΨ. In this paper, we show that EΨ(G)=|G|+DΨ(G)−1.  相似文献   

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

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