The Roller-Coaster Conjecture Revisited

Levit, Vadim; Mandrescu, Eugen
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1499
Academic Journal
A graph is well-covered if all its maximal independent sets are of the same cardinality (Plummer in J Comb Theory 8:91-98, 1970). If G is a well-covered graph with at least two vertices, and $$G{-}v$$ is well-covered for every vertex v, then G is a 1- well-covered graph (Staples in On some subclasses of well-covered graphs. Ph.D. Thesis, Vanderbilt University, 1975). The graph G is $$\lambda $$ - quasi-regularizable if $$\lambda >0$$ and $$\lambda \cdot \vert S\vert \le \vert N( S) \vert $$ for every independent set S of G. It is known that every well-covered graph without isolated vertices is 1-quasi-regularizable (Berge in Ann Discret Math 12:31-44, 1982). The independence polynomial $$I(G;x)= {\sum _{k=0}^{\alpha }} s_{k}x^{k}$$ is the generating function of independent sets in a graph G (Gutman and Harary in Util Math 24:97-106, 1983), where $$\alpha $$ is the independence number of G. The Roller-Coaster Conjecture (Michael and Traves in Graphs Comb 19:403-411, 2003), saying that for every permutation $$\sigma $$ of the set $$\{\lceil \frac{\alpha }{2}\rceil ,\ldots ,\alpha \}$$ there exists a well-covered graph G with the independence number $$\alpha $$ such that the coefficients $$( s_{k}) $$ of I( G; x) satisfy has been validated in Cutler and Pebody (J Comb Theory A 145:25-35, 2017). In this paper we show that independence polynomials of $$\lambda $$ -quasi-regularizable graphs are partially unimodal. More precisely, the coefficients of an upper part of I( G; x) are in non-increasing order. Based on this finding, we prove that the unconstrained part of the independence sequence is: for well-covered graphs, and for 1-well-covered graphs, where $$\alpha $$ stands for the independence number, and n is the cardinality of the vertex set.


Related Articles

  • Further Properties of Trees with Minimal Atom-Bond Connectivity Index. Jianping Liu; Jinsong Chen // Abstract & Applied Analysis;2014, p1 

    Let G = (V, E) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights ((du + dv - 2 ) /dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we...

  • Some Properties on Estrada Index of Folded Hypercubes Networks. Jia-Bao Liu; Xiang-Feng Pan; Jinde Cao // Abstract & Applied Analysis;2014, p1 

    Let G be a simple graph with n vertices and let λ1, λ2,...,λn be the eigenvalues of its adjacency matrix; the Estrada index EE(G) of the graph G is defined as the sum of the terms eλi, i = 1,2,...,n. The n-dimensional folded hypercube networks FQn are an important and attractive...

  • Vertex Equitable Labeling of Cycle and Star Related Graphs. Jeyanthi, P.; Maheswari, A.; Vijayalaksmi, M. // Journal of Scientific Research;2015, Vol. 7 Issue 3, p33 

    Let G be a graph with p vertices and q edges and A = 0,1,2,..., A vertex labeling f: V (G) -> A induces an edge labeling f* defined by f*(uv) = f(u) + f(v) for all edges uv. For a∈ A, let vf (a) be the number of vertices v with f(v) = a. A graph G is said to be vertex equitable if there...

  • On (k,kn-k2-2k-1)-Choosability of n-Vertex Graphs. Charoenpanitseri, Wongsakorn // International Journal of Mathematics & Mathematical Sciences;5/12/2015, Vol. 2015, p1 

    A (k,t)-list assignment L of a graph G is a mapping which assigns a set of size k to each vertex v of G and |⋃v∈V(G)‍L(v)|=t. A graph G is (k,t)-choosable if G has a proper coloring f such that f(v)∈L(v) for each (k,t)-list assignment L. In 2011, Charoenpanitseri et al....

  • Some Results on Vertex Version and Edge Versions of Modified Schultz Index. Azari, Mahdieh // International Journal of Mathematical Combinatorics;2016, Vol. 2, p65 

    Let G1 and G2 be two simple connected graphs with disjoint vertex sets V(G1) and V(G2), respectively. For given vertices a1 G V(G1) and a2 ∈ V(G2), a splice of ∈1 and G2 by vertices a1 and a2 is defined by identifying the vertices a1 and a2 in the union of G1 and G2 and a link of G1...

  • A note on the augmented Zagreb index of cacti with fixed number of vertices and cycles. Ali, Akbar; Bhatti, Akhlaq A. // Kuwait Journal of Science;2016, Vol. 43 Issue 4, p11 

    Recent studies show that augmented Zagreb index ( AZI ) possess the best correlating ability among various well known topological indices for predicting the certain physicochemical properties of particular types of molecules. Hence, it is meaningful to study the mathematical properties of AZI...

  • On 3-Regular Bipancyclic Subgraphs of Hypercubes. Borse, Y. M.; Shaikh, S. R. // International Journal of Combinatorics;5/5/2015, Vol. 2015, p1 

    The n-dimensional hypercube Qn is bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qn  (n≥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.

  • The Minimum Equitable Domination Energy of a Graph. Rajendra, P.; Rangarajan, R. // International Journal of Mathematical Combinatorics;Sep2015, Vol. 3, p62 

    A subset D of V is called an equitable dominating set [8] if for every v ∈ V -D there exists a vertex u ∈ D such that uv ∈ E(G) and |deg(u) - deg(v)| ≤ 1, where deg(u) denotes the degree of vertex u and deg(v) denotes the degree of vertex v. Recently, The minimum covering...

  • Reduction Theorem for Lattice Cohomology. László, Tamás; Némethi, András // IMRN: International Mathematics Research Notices;2015, Vol. 2015 Issue 11, p2938 

    The lattice cohomology of a plumbed 3-manifold M associated with a connected negative definite plumbing graph is an important tool in the study of topological properties of M and in the comparison of the topological properties with analytic ones, whenever M is realized as complex analytic...

  • Semientire Equitable Dominating Graphs. Basavanagoud, B.; Kulli, V. R.; Teli, Vijay V. // International Journal of Mathematical Combinatorics;Sep2014, Vol. 3, p49 

    The semientire equitable dominating graph SEqD(G) of a graph G = (V, E) is the graph with vertex set V⋃S, where S is the collection of all minimal equitable dominating sets of G and with two vertices u, v G V⋃S adjacent if u, v∊D, where D is the minimal equitable dominating set...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics