×

Graphs whose independence fractals are line segments. (English) Zbl 1460.05142

Summary: Let \(G\) be a simple graph. By an independent set in \(G\), we mean a set of pairwise non-adjacent vertices in \(G\). The independence polynomial of \(G\) is defined as \(I_G(z)=i_0+i_1z+i_2 z^2+\cdots+i_\alpha z^{\alpha}\), where \(i_m=i_m(G)\) is the number of independent sets in \(G\) with cardinality \(m\) and \(\alpha=\alpha(G)\) denotes the cardinality of a largest independent set in \(G\) (known as the independence number of \(G)\). Let \(G^k\) denote the \(k\)-times lexicographic product of \(G\) with itself. The set of roots of \(I_{G^k}\) is known to converge as \(k\) tends to \(\infty\), with respect to the Hausdorff metric, and the limiting set is known as the independence attractor. The independence fractal of a graph is the limiting set of roots of the reduced independence polynomial \(I_{G^k}-1\) of \(G^k\) as \(k\) tends to \(\infty\). In this article, we consider the independence fractals of graphs with independence number 3. We attempt to find all such graphs whose independence fractal is a line segment. It is shown that the independence fractal and the independence attractor coincide when the earlier is a line segment. The line segment turns out to be an interval \([-\frac{4}{k}, 0]\) for \(k\in\{1,2,3,4\}\). It is found that each of these graphs have 9 vertices and there are exactly 13 such disconnected graphs. We show that there does not exist any connected graph for \(k=4\). For \(k=1\), there are 17 such connected graphs and for \(k=2,3\) the number is quite large.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C31 Graph polynomials
05C76 Graph operations (line graphs, products, etc.)
28A80 Fractals
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alikhani, S.; Peng, Y., Independence roots and independence fractals of certain graphs, J. Appl. Math. Comput., 36, 1-2, 89-100 (2011) · Zbl 1222.05107 · doi:10.1007/s12190-010-0389-4
[2] Beardon, AF, Iteration of Rational Functions (1991), Berlin: Springer, Berlin · Zbl 0742.30002 · doi:10.1007/978-1-4612-4422-6
[3] Beaton, I.; Brown, JI; Cameron, B., Independence equivalence classes of paths and cycles, Australas. J. Combin., 75, 127-145 (2019) · Zbl 1429.05152
[4] Bollobas, B., Modern Graph Theory (1998), Berlin: Springer, Berlin · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4
[5] Brown, JI; Hickman, CA; Nowakowski, RJ, The independence fractal of a graph, J. Comb. Theory Ser. B, 87, 209-230 (2003) · Zbl 1050.05090 · doi:10.1016/S0095-8956(02)00014-X
[6] Brown, JI; Hickman, CA; Nowakowski, RJ, On the location of the roots of independence polynomials, J. Algebraic Combin., 19, 273-282 (2004) · Zbl 1043.05087 · doi:10.1023/B:JACO.0000030703.39946.70
[7] Chudnovsky, M.; Seymour, P., The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B, 97, 3, 350-357 (2007) · Zbl 1119.05075 · doi:10.1016/j.jctb.2006.06.001
[8] Csikvari, P., Note on the smallest root of the independence polynomial, Comb. Probab. Comput., 22, 1, 1-8 (2013) · Zbl 1257.05066 · doi:10.1017/S0963548312000302
[9] Gutman, I.; Harary, F., Generalizations of the matching polynomial, Utilitas Math., 24, 97-106 (1983) · Zbl 0527.05055
[10] Zhang, H., A way to construct independence equivalent graphs, Appl. Math. Lett., 25, 10, 1304-1308 (2012) · Zbl 1248.05087 · doi:10.1016/j.aml.2011.11.033
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.