Optimal graphs for independence and \(k\)-independence polynomials. (English) Zbl 1402.05106
Summary: The independence polynomial \(I(G, x)\) of a finite graph \(G\) is the generating function for the sequence of the number of independent sets of each cardinality. We investigate whether, given a fixed number of vertices and edges, there exists optimally-least (optimally-greatest) graphs, that are least (respectively, greatest) for all non-negative \(x\). Moreover, we broaden our scope to \(k\)-independence polynomials, which are generating functions for the \(k\)-clique-free subsets of vertices. For \(k \geq 3\), the results can be quite different from the \(k = 2\) (i.e. independence) case.
MSC:
| 05C31 | Graph polynomials |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Ath, Y., Sobel, M.: Some conjectured uniformly optimal reliable networks. Probab. Eng. Inform. Sci. 14, 375-383 (2011) · Zbl 0996.90011 |
| [2] | Culter, J., Radcliffe, A.J.: Extremal problems for independent set enumeration. Electr. J. Comb. 14, 1-17 (2000) |
| [3] | Aigner, M., Ziegler, G.M.: Proofs from The Book, 5th edn. Springer, New York (2014) · Zbl 1294.01001 |
| [4] | Boesch, F.T., Satyanarayana, A., Suffel, C.L.: Least reliable networks and the reliability domination. IEEE Trans. Comm. 38, 2004-2009 (1990) · Zbl 0735.90039 · doi:10.1109/26.61483 |
| [5] | Boesch, F., Li, X., Suffel, C.: On the existence of uniformly optimally reliable networks. Networks 21, 181-194 (1991) · Zbl 0721.90038 · doi:10.1002/net.3230210204 |
| [6] | Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978) · Zbl 0419.05031 |
| [7] | Brown, J.I.: Discrete Structures and Their Interactions. CRC, Boca Raton (2013) · Zbl 1277.06001 |
| [8] | Brown, J.I., Cox, D.: Nonexistence of optimal graphs for all terminal reliability. Networks 63, 146-153 (2014) · Zbl 1386.05188 · doi:10.1002/net.21530 |
| [9] | Brown, J.I., Hoshino, R.: Independence polynomials of circulants with an application to music. Discrete Math. 309, 2292-2304 (2009) · Zbl 1228.05178 · doi:10.1016/j.disc.2008.05.003 |
| [10] | Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press, New York (1987) |
| [11] | Gross, D., Saccoman, J.T.: Uniformly optimal reliable graphs. Networks 31, 217-225 (1998) · Zbl 1015.68135 · doi:10.1002/(SICI)1097-0037(199807)31:4<217::AID-NET2>3.0.CO;2-G |
| [12] | Herzog, J., Hibi, T.: Componentwise Linear Ideals. Nagoya Math. J. 153, 141-159 (1999) · Zbl 0930.13018 · doi:10.1017/S0027763000006930 |
| [13] | Hoefel, A.: Hilbert Functions in Monomial Algebras, Ph.D. Disseratation, Dalhousie University (2011) |
| [14] | Gutman, I., Harary, F.: Generalizations of the matching polynomial. Utilitas Mathematica 24, 97-106 (1983) · Zbl 0527.05055 |
| [15] | Katona, G.; Erdös, P. (ed.); Katona, G. (ed.), A Theorem of finite sets, 187-207 (1966), Budapest · Zbl 0313.05003 |
| [16] | Kruskal, JB; Bellman, R. (ed.), The number of simplicies in a complex, 251-278 (1963), Berkeley · Zbl 0116.35102 |
| [17] | Levit, V.E.: The independence polynomial of a graph—a survey. In: Bozapalidis, S., Kalampakas, A., Rahonis, G. (eds.) Proceedings of the First Annual Conference on Algebraic Informatics, pp. 233-254. Aristotle University of Thessaloniki, Greece (2005) |
| [18] | Lovász, L., Simonovits, M.: On the number of complete subgraphs of a graph. Congr. Numer. 15, 431-441 (1976) · Zbl 0339.05115 |
| [19] | Macaulay, R.: Some Properties of Enumeration in Theory of Modular Systems. Proc. Lond. Math. Soc. 26, 531-555 (1927) · JFM 53.0104.01 · doi:10.1112/plms/s2-26.1.531 |
| [20] | Mermin, J.: Lexicographic Ideals, Ph.D. Dissertation, Cornell University (2006) · Zbl 1113.13012 |
| [21] | Myrvold, W., Cheung, K.H., Page, L.B., Perry, J.E.: Uniformly most reliable networks do not always exist. Networks 21, 417-419 (1991) · Zbl 0729.90045 · doi:10.1002/net.3230210404 |
| [22] | Sakaloglu, A., Satyanarayana, A.: Graphs with the least number of colourings. J. Graph Theory 19, 523-533 (1995) · Zbl 0830.05029 · doi:10.1002/jgt.3190190407 |
| [23] | Simonelli, I.: Optimal graphs for chromatic polynomials. Discrete Math. 308(11), 2228-2239 (2008) · Zbl 1138.05028 · doi:10.1016/j.disc.2007.04.069 |
| [24] | Stanley, R.P.: The upper bound conjecture and cohen-macaulay rings. Stud. Appl. Math. 54, 135-142 (1975) · Zbl 0308.52009 · doi:10.1002/sapm1975542135 |
| [25] | Fisher, D., Solow, A.: Dependence polynomials. Discrete Math. 82, 251-258 (1990) · Zbl 0721.05036 · doi:10.1016/0012-365X(90)90202-S |
| [26] | Jonsson, J.: Simplicial Complexes of Graphs. Springer, New York (2008) · Zbl 1152.05001 · doi:10.1007/978-3-540-75859-4 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
