On the unimodality of independence polynomials of very well-covered graphs

The independence polynomial $i(G,x)$ of a graph $G$ is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $n∕2$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.     

On rank-perfect subclasses of near-bipartite graphs

Shepherd95 proved that the stable set polytopes of near-bipartite graphs are given by constraints associated with the complete join of antiwebs only. For antiwebs, the facet set reduces to rank constraints associated with single antiwebs by Wagler2004. We extend this result to a larger graph class, the complements of fuzzy circular interval graphs, recently introduced in ChudnovskySeymour2004. Received: November 2004 / Revised version: June 2005     

Shedding vertices of vertex decomposable well-covered graphs

We focus our attention on well-covered graphs that are vertex decomposable. We show that for many known families of these vertex decomposable graphs, the set of shedding vertices forms a dominating set. We then construct three new infinite families of well-covered graphs, none of which have this property. We use these results to provide a minimal counterexample to a conjecture of Villarreal regarding Cohen–Macaulay graphs.     

Subdivisions,parity and well-covered graphs

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: “given a graph G which is a parity graph, is G also well-covered graph?” is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (Quaestiones Math. 16 (1993)) and Finbow, Hartnell, and Whitehead (Discrete Math. 125 (1994)). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 85–94, 1997     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

Vertex decomposability and regularity of very well-covered graphs

A graph is called very well-covered if it is unmixed without isolated vertices such that the cardinality of each minimal vertex cover is half the number of vertices. We first prove that a very well-covered graph is Cohen-Macaulay if and only if it is vertex decomposable. Next, we show that the Castelnuovo-Mumford regularity of the quotient ring of the edge ideal of a very well-covered graph is equal to the maximum number of pairwise 3-disjoint edges.     

A class of planar well-covered graphs with girth four

A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1-well-covered graph was introduced by Staples in her 1975 dissertation: a well-covered graph G is 1-well-covered if and only if G - v is also well covered for every point v in G. Except for K₂ and C₅, every 1-well-covered graph contains triangles or 4-cycles. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.     

On some subclasses of P‐matrices

A matrix with positive row sums and all its off‐diagonal elements bounded above by their corresponding row averages is called a B‐matrix by J. M. Peña in References (SIAM J. Matrix Anal. Appl. 2001; 22 :1027–1037) and (Numer. Math. 2003; 95 :337–345). In this paper, it is generalized to more extended matrices—MB‐matrices, which is proved to be a subclass of the class of P‐matrices. Subsequently, we establish relationships between defined and some already known subclasses of P‐matrices (see, References SIAM J. Matrix Anal. Appl. 2000; 21 :67–78; Linear Algebra Appl. 2004; 393 :353–364; Linear Algebra Appl. 1995; 225 :117–123). As an application, some subclasses of P‐matrices are used to localize the real eigenvalues of a real matrix. Copyright © 2007 John Wiley & Sons, Ltd.     

A characterization of well-covered graphs in terms of prohibited costable subgraphs

A graph is calledwell-covered if all maximal independent subsets in it have the same number of elements. LetI be an independent subset (possibly empty) in a graphG. The subgraph ofG obtained by erasing the setI together with its neighborhood is calledcostable. We present a characterization of the class of well-covered graphs in terms of the minimal set of prohibited costable subgraphs. This characterization implies characterizations of some well-known subclasses of the class of well-covered graphs as well as the existence of a polynomial algorithm for the recognition of well-covered graphs with bounded valences. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 52–56, January, 2000.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

On some weakly bipartite graphs

We characterize a class of weakly bipartite graphs. In this case, the max-cut problem can be solved by finding a minimum two-commodity cut.     

关于某些P-叶解析函数类的系数估计

利用拟从属关系引进了一些新的P-叶解析函数的子类,应用解析函数的基本不等式和分析技巧,讨论了相应函数类的系数估计,得到了准确结果,推广了一些相关结果,并给出了Hadamard卷积在Fekete-Szeg问题上的应用.     

On some properties of o-degeneracy graphs

Degenerate optima in linear programming problems lead in a canonical way to so-called o-degeneracy graphs as subgraphs of degeneracy graphs induced by the set of optimal bases. Fundamental questions about the structure of o-degeneracy graphs suggest the closer inspection of some properties of these graphs, such as, for example, the connectivity and the complexity. Finally, some open questions are pointed out.     

On well-covered triangulations: Part III

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.