共查询到20条相似文献,搜索用时 406 毫秒
1.
2.
最近Klaus Dohmen等人提出新的双变量色多项式概念,对此,本文提出—个—般性的减边公式.通过反复运用该公式,可以方便求得任何简单图的双变量色多项式.由此减边公式,研究了一些特殊图和多分支图的双变量色多项式公式.本文还研究了由互不相连的多个子图都与某个顶点相连而成的图的双变量色多项式计算的删点公式以及简单图的双变量色多项式系数和问题.进而,本文提出—个新概念—正则树.利用这个减边公式,研究了正则树的双变量色多项式计算公式和—些性质,以及正则树整子图的双变量色多项式公式及其有关性质. 相似文献
3.
4.
5.
图的色多项式系数之和问题的研究 总被引:2,自引:0,他引:2
本文给出了任何简单图G(V,E)的色多项式P(G,λ)=∑i=1^vαiλ^i系数之和的公式:∑i=1^vαi={0ε≠0 1ε=0;并进行了证明,从而为判别一个多项式不是图的色多项式提供了一个必要条件.同时也分别给出了树、2-树、圈、轮图和完全图的色多项式系数绝对值之和的表达式.最后证明了任何简单连通图的色多项式系数绝对值之和∑i=1^v|αi|与边ε成正比,且必满足2^v-1≤∑i=1^v|αi|≤пi=1^vi. 相似文献
6.
图G为具有m条边的连通图,E(G)={e1,e2,…,em},H={H1,H2,…,Hm}为由m个连通图构成的集合.图G[H]为G与H的张量积图,即对每个i(1≤i≤m),ei被Hi替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了G[H]的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目. 相似文献
7.
8.
直径为5,6的整树的一些新类 总被引:4,自引:0,他引:4
设 G 是图,P(G,x)是图 G 的特征多项式.1974年,F.Harary 和 A.J.Schwenk首先引入了整图的概念,即图 G 的特征方程 P(G,x)=0的所有解都是整数.1987年,我们解决了直径3的树 T(m,r)是否为整树的问题,这里 T(m,r)是由一条新边联结两个星图 K_(1,m)和 K_(1,r)的中心得到的图.这个问题是文献[2]中第23个问题的一部分.对于直径为4的情形,文献[2]给出了当且仅当 m 和 m+r 都是平方数时,S(r,m) 相似文献
9.
一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值. 相似文献
10.
讨论了ω,q-Bernstein多项式的Voronovskaya-型公式及其收敛的饱和性.给出了当0
1[0,1]时ω,q-Bernstein多项式的Voronovskaya-型公式.如果0<ω,q<1,f∈C1[0,1]时ω,q-Bernstein多项式的Voronovskaya-型公式.如果0<ω,q<1,f∈C1[0,1],则ω,q-Bernstein多项式的收敛阶为o(q1[0,1],则ω,q-Bernstein多项式的收敛阶为o(qn)当且仅当((f(1-qn)当且仅当((f(1-q(k-1)-f(1-q)(k-1)-f(1-q)k))/((1-qk))/((1-q(k-1)-(1-q(k-1)-(1-qk)))=f'(1-qk)))=f'(1-qk),k=1,2,…还证明f如果f在[0,1]是凸的或者在(-ε,1+ε)(ε>0)解析,则ω,q-Bernstein多项式的收敛阶为o(qk),k=1,2,…还证明f如果f在[0,1]是凸的或者在(-ε,1+ε)(ε>0)解析,则ω,q-Bernstein多项式的收敛阶为o(qn)当且仅当f是线性函数. 相似文献
11.
A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function. 相似文献
12.
A simple graph is said to be of class 1 or of class 2 according as its chromatic index equals the maximum degree or is one greater. A graph of class 2 is called critical if all its proper subgraphs have smaller chromatic index. It has been conjectured by Beineke and Wilson and by Jakobsen that all critical graphs have odd order. In this paper we verify the truth of this conjecture for all graphs of order less than 12 and all graphs of order 12 and maximum degree 3. We also determine all critical graphs through order 7. 相似文献
13.
In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that
induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced
subgraphs of C-I graphs of posets is polynomial. 相似文献
14.
Irene Sciriha 《Linear algebra and its applications》2009,430(1):78-85
In this paper, we consider graphs whose deck consists of cards (which are the vertex-deleted subgraphs) that share the same eigenvalue, say μ. We show that, the characteristic polynomial can be reconstructed from the deck, providing a new proof of Tutte’s result for this class of graphs. Moreover, for the subclass of non-singular graphs, the graph can be uniquely reconstructed from the eigenvectors of the cards associated with the eigenvalue μ. The remaining graphs in this class are shown to be μ-cores graphs. 相似文献
15.
This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph G, and demonstrates how these critical subgraphs can be used to determine the chromatic number of G. Computational experiments are reported on random and DIMACS benchmark graphs to compare the proposed algorithms, as well as to find lower bounds on the chromatic number of these graphs. We improve the best known lower bound for some of these graphs, and we are even able to determine the chromatic number of some graphs for which only bounds were known. 相似文献
16.
The relation of chromatic aspects and the existence of certain induced subgraphs of a triangle-free graph will be investigated. Based on a characterization statement of Pach, some results on the chromatic number of triangle-free graphs with certain forbidden induced subgraphs will be refined by describing their structure in terms of homomorphisms. In particular, we introduce chordal triangle-free graphs as a natural superclass of chordal bipartite graphs and describe the structure of the maximal triangle-free members. Finally, we improve on the upper bound for the chromatic number of triangle-free sK2-free graphs by 1 for s2 giving the tight bound for s=3. 相似文献
17.
Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph. We extend our construction and categorify the Bollobás-Riordan polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification. 相似文献
18.
It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique. 相似文献
19.
Steve Kirkland 《Linear algebra and its applications》2007,423(1):3-21
A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class. 相似文献
20.
Erich Prisner 《Combinatorica》2000,20(1):109-117
Bicliques are inclusion-maximal induced complete bipartite subgraphs in graphs. Upper bounds on the number of bicliques in bipartite
graphs and general graphs are given. Then those classes of graphs where the number of bicliques is polynomial in the vertex
number are characterized, provided the class is closed under induced subgraphs.
Received January 27, 1997 相似文献