共查询到20条相似文献,搜索用时 0 毫秒
1.
Let G be a well covered graph, that is, all maximal independent sets of G have the same cardinality, and let ik denote the number of independent sets of cardinality k in G. We investigate the roots of the independence polynomial i(G, x) = ikxk. In particular, we show that if G is a well covered graph with independence number , then all the roots of i(G, x) lie in in the disk |z| (this is far from true if the condition of being well covered is omitted). Moreover, there is a family of well covered graphs (for each ) for which the independence polynomials have a root arbitrarily close to –. 相似文献
2.
Eugen Mandrescu 《Graphs and Combinatorics》2009,25(4):545-556
A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is where s k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).
Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic). 相似文献
$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$
3.
4.
5.
Annals of Combinatorics - For a poset whose Hasse diagram is a rooted plane forest F, we consider the corresponding tree descent polynomial $$A_F(q)$$, which is a generating function of the number... 相似文献
6.
The independence polynomial of a (finite) graph is the generating function for the number of independent sets of each cardinality. Assuming that each possible edge of a complete graph of order n is independently operational with probability p, we consider the expected independence polynomial. We show here that for all fixed , the expected independence polynomials of complete graphs have all real, simple roots. 相似文献
7.
The independence polynomial of a graph G is the function i(G, x) =
k0
i
k
x
k, where i
k is the number of independent sets of vertices in G of cardinality k. We prove that real roots of independence polynomials are dense in (–, 0], while complex roots are dense in , even when restricting to well covered or comparability graphs. Throughout, we exploit the fact that independence polynomials are essentially closed under graph composition. 相似文献
8.
Swanepoel 《Discrete and Computational Geometry》2008,28(4):649-670
Abstract. We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n . 相似文献
9.
Swanepoel 《Discrete and Computational Geometry》2002,28(4):649-670
Abstract. We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n . 相似文献
10.
Bounds for the Independence Number of Critical Graphs 总被引:1,自引:0,他引:1
Brinkmann Gunnar; Choudum Sheshayya A.; Grunewald Stefan; Steffen Eckhard 《Bulletin London Mathematical Society》2000,32(2):137-140
In 1968 Vizing conjectured that any independent vertex set ofan edge-chromatic critical graph G contains at most half ofthe vertices of G, that is, (G|(G)|). Let be the maximum vertexdegree in a critical graph. For each , we determine c() suchthat (G)c()|V)|. 1991 Mathematics Subject Classification 05C15,05C70. 相似文献
11.
12.
Adam Bohn 《Graphs and Combinatorics》2014,30(2):287-301
We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root. 相似文献
13.
14.
王春香 《数学物理学报(A辑)》2009,29(1):145-150
如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K4) 且不含诱导子图K4-e, 则 β(G) =n/3. 相似文献
15.
Satoshi Fujita 《Mathematics in Computer Science》2010,3(1):31-38
This paper introduces a new definition of embedding a local structure to a given network, called loose cover of graphs. We derive several basic properties on the notion of loose cover, which includes transitivity, maximality, and the computational complexity of finding a loose cover by paths and cycles. In particular, we show that the decision problem is in P if the given local structure is a path with three or less vertices, while it is NP-complete for paths consisting of six or more vertices. 相似文献
16.
We say that a graph G is T-unique if any other graph having the same Tutte polynomial as G is necessarily isomorphic to G. In this paper we show that several well-known families of graphs are T-unique: wheels, squares of cycles, complete multipartite graphs, ladders, Möbius ladders, and hypercubes. In order to prove these results, we show that several parameters of a graph, like the number of cycles of length 3, 4 and 5, and the edge-connectivity are determined by its Tutte polynomial.Research partially supported by projects BFM2001-2340 and by CUR Gen. Cat. 1999SGR00356Final version received: January 10, 2003 相似文献
17.
Sharp Inequalities for the Product of Polynomials 总被引:4,自引:0,他引:4
Let f1(z),..., fm(z) be polynomials with complex coefficients,and let their product be of degree n. For any polynomial, let||f|| be the maximum of |f(z)| on the unit circle. We determineconstants Cm < 2 for which for any n. The inequalities are asymptotically sharp as n .This improves earlier results of Gel'fond and Mahler, who gavethe constants e and 2 respectively. If f1,..., fm have realcoefficients, we show that for all m 2 and that this is asymptotically sharp. That is,in the real case, the best constant does not depend upon m form 2. 相似文献
18.
A set S of vertices of a graph G is dominating if each vertex x not in S is adjacent to some vertex in S, and is independent if no two vertices in S are adjacent. The domination number, γ(G), is the order of the smallest dominating set in G. The independence number, α(G), is the order of the largest independent set in G. In this paper we characterize bipartite graphs and block graphs G for which γ(G) = α(G). 相似文献
19.
20.
通过讨论几类图簇匹配多项式的因式分解,给出了两类图簇匹配等价图的结构性质,从而得到几类新的非匹配唯一图. 相似文献