Independence polynomials of circulants with an application to music. (English) Zbl 1228.05178
Summary: The independence polynomial of a graph \(G\) is the generating function \(I(G,x)=\sum _{k\geq 0}i_{k}x^{k}\), where \(i_k\) is the number of independent sets of cardinality \(k\) in \(G\). We show that the problem of evaluating the independence polynomial of a graph at any fixed non-zero number is intractable, even when restricted to circulants. We provide a formula for the independence polynomial of a certain family of circulants, and its complement. As an application, we derive a formula for the number of chords in an \(n\)-tet musical system (one where the ratio of frequencies in a semitone is \(2^{1/n}\)) without ‘close’ pitch classes.
MSC:
| 05C31 | Graph polynomials |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C90 | Applications of graph theory |
References:
| [1] | Berge, C., Motivations and history of some of my conjectures, Discrete Mathematics, 165, 61-70 (1997) · Zbl 0873.05066 |
| [2] | Bermond, J.-C.; Peyrat, C., Induced subgraphs of the power of a cycle, SIAM Journal on Discrete Mathematics, 2, 452-455 (1989) · Zbl 0708.05060 |
| [3] | Bondy, J. A.; Locke, S. C., Triangle-free subgraphs of powers of cycles, Graphs and Combinatorics, 8, 109-118 (1992) · Zbl 0769.05047 |
| [4] | Broere, I.; Hattingh, J. H., Products of circulant graphs, Quaestiones Mathematica, 13, 191-216 (1990) · Zbl 0744.05058 |
| [5] | Brown, J. I.; Dilcher, K.; Nowakowski, R. J., Roots of independence polynomials of well covered graphs, Journal of Algebraic Combinatorics, 11, 197-210 (2000) · Zbl 0994.05109 |
| [6] | Brown, J. I.; Hickman, C. A.; Nowakowski, R. J., On the location of roots of independence polynomials, Journal of Algebraic Combinatorics, 19, 273-282 (2004) · Zbl 1043.05087 |
| [7] | Brown, J. I.; Hickman, C. A.; Nowakowski, R. J., The independence fractal of a graph, Journal of Combinatorial Theory Series B, 87, 209-230 (2003) · Zbl 1050.05090 |
| [8] | Brown, J. I.; Nowakowski, R. J., Bounding the roots of independence polynomials, Ars Combinatoria, 58, 113-120 (2001) · Zbl 1065.05051 |
| [9] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Annals of Mathematics, 164, 51-229 (2006) · Zbl 1112.05042 |
| [10] | Chvátal, V., On the strong perfect graph conjecture, Journal of Combinatorial Theory Series B, 20, 139-141 (1976) · Zbl 0293.05117 |
| [11] | Codenotti, B.; Gerace, I.; Vigna, S., Hardness results and spectral techniques for combinatorial problems on circulant graphs, IEEE Transactions on Computers, 48, 345-351 (1999) · Zbl 1391.94908 |
| [12] | Diestel, R., Graph Theory (2000), Springer-Verlag: Springer-Verlag New York · Zbl 0945.05002 |
| [13] | Dohmen, K.; Pönitz, A.; Tittmann, P., A new two-variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical Computer Science, 6, 69-89 (2003) · Zbl 1035.68078 |
| [14] | Fisher, D. C.; Solow, A. E., Dependence polynomials, Discrete Mathematics, 82, 251-258 (1990) · Zbl 0721.05036 |
| [15] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of \(N P\)-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039 |
| [16] | Gutman, I., Graphs with maximum and minimum independence numbers, Publications Institut Mathematique (Belgrade), 34, 73-79 (1983) · Zbl 0554.05038 |
| [17] | Gutman, I.; Harary, F., Generalizations of the matching polynomial, Utilitas Mathematica, 24, 97-106 (1983) · Zbl 0527.05055 |
| [18] | Gutman, I., On independent vertices and edges of belt graphs, Publications Institut Mathematique (Belgrade), 59, 11-17 (1996) · Zbl 0942.05052 |
| [19] | Gutman, I., Numbers of independent vertex and edge sets of a graph: Some analogies, Graph Theory Notes of New York, 22, 18-22 (1992) |
| [20] | Gutman, I., Some analytic properties of the independence and matching polynomials, MATCH, 28, 139-150 (1992) · Zbl 0767.05070 |
| [21] | Gutman, I., An identity for the independence polynomials of trees, Publications Institut Mathematique (Belgrade), 50, 19-23 (1991) · Zbl 0763.05026 |
| [22] | Gutman, I., On independent vertices and edges in a graph, (Bodendeik, R.; Henn, R., Topics in Combinatorics and Graph Theory (1990), Physica-Verlag: Physica-Verlag Heidelberg) · Zbl 0697.05038 |
| [23] | Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the computational complexity of the Jones and Tutte polynomials, Mathematical Proceedings of the Cambridge Philosophical Society, 108, 35-53 (1990) · Zbl 0747.57006 |
| [24] | Krivelevich, M.; Nachmias, A., Colouring powers of cycles from random lists, European Journal of Combinatorics, 25, 961-968 (2004) · Zbl 1050.05053 |
| [25] | Lin, C.; Lin, J.-J.; Shyu, T.-W., Isomorphic star decompositions of multicrowns and the power of cycles, Ars Combinatoria, 53, 249-256 (1999) · Zbl 0994.05113 |
| [26] | Locke, S. C., Further notes on: Largest triangle-free subgraphs in powers of cycles, Ars Combinatoria, 49, 65-77 (1998) · Zbl 0963.05067 |
| [27] | Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 2, 253-267 (1972) · Zbl 0239.05111 |
| [28] | Michael, T. S.; Traves, W. N., Independence sequences of well-covered graphs: Non-unimodality and the roller-coaster conjecture, Graphs and Combinatorics, 19, 403-411 (2003) · Zbl 1022.05056 |
| [29] | Sethares, W., Tuning, Timber, Spectrum, Scale (2005), Springer-Verlag: Springer-Verlag New York |
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.
