Symmetry 2011, 3(3), 472-486; doi:10.3390/sym3030472
Article

On Symmetry of Independence Polynomials

1,*  and 2
Received: 27 April 2011; in revised form: 20 June 2011 / Accepted: 22 June 2011 / Published: 15 July 2011
(This article belongs to the Special Issue Symmetry Measures on Complex Networks)
This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract: An independent set in a graph is a set of pairwise non-adjacent vertices, and α(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while μ(G) is the cardinality of a maximum matching. If sk is the number of independent sets of size k in G, then I(G; x) = s0 + s1x + s2x2 + ... + sαxα, α = α (G), is called the independence polynomial of G (Gutman and Harary, 1986). If sj = sαj for all 0 ≤ j ≤ [α/2], then I(G; x) is called symmetric (or palindromic). It is known that the graph G ° 2K1, obtained by joining each vertex of G to two new vertices, has a symmetric independence polynomial (Stevanović, 1998). In this paper we develop a new algebraic technique in order to take care of symmetric independence polynomials. On the one hand, it provides us with alternative proofs for some previously known results. On the other hand, this technique allows to show that for every graph G and for each non-negative integer k ≤ μ (G), one can build a graph H, such that: G is a subgraph of H, I (H; x) is symmetric, and I (G ° 2K1; x) = (1 + x)k · I (H; x).
Keywords: independent set; independence polynomial; symmetric polynomial; palindromic polynomial
Download PDF Full-Text [275 KB, uploaded 15 July 2011 12:12 CEST]

Export to BibTeX |
EndNote


MDPI and ACS Style

Levit, V.E.; Mandrescu, E. On Symmetry of Independence Polynomials. Symmetry 2011, 3, 472-486.

AMA Style

Levit VE, Mandrescu E. On Symmetry of Independence Polynomials. Symmetry. 2011; 3(3):472-486.

Chicago/Turabian Style

Levit, Vadim E.; Mandrescu, Eugen. 2011. "On Symmetry of Independence Polynomials." Symmetry 3, no. 3: 472-486.

Symmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert
{"cc_re__cc_re__cc_by_3_0": ["y of Independence Polynomials\">\n\n            <meta name=\"dc.creator\" content=\"Vadim E. Levit\">\n            <meta name=\"dc.creator\" content=\"Eugen Mandrescu\">\n        \n    <meta name=\"dc.type\" content=\"Article\">\n    <meta name=\"dc.source\" content=\"Symmetry 2011, Vol. 3, Pages 472-486\">\n    <meta name=\"dc.date\" content=\"2011-07-15\">\n            <meta name =\"dc.identifier\" content=\"10.3390/sym3030472\">\n    \n    <meta name=\"dc.publisher\" content=\"Molecular Diversity Preservation International\">\n    <meta name=\"dc.rights\" content=\"http://creativecommons.org/licenses/by/3.0/\">\n    <meta name=\"dc.format\" content=\"application/pdf\" >\n    <meta name=\"dc.language\" content=\"en\" >\n\t<meta name=\"dc.description\" content=\"An independent set in a graph is a set of pairwise non-adjacent vertices, and \u03b1(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while \u03bc(G) is the cardinality of a maximum matching. If sk is the number of independent sets of size k in G, then I(G; x) = s0 + s1x + s2x2 + ... + s\u03b1x\u03b1, \u03b1 = \u03b1 (G), is calle", "  \t\t  \t\t\t\t</div>\n\n\t\t<div class=\"corspnd\">* Author to whom correspondence should be addressed. </div></div>\n\n<div class=\"art-pubhistory\">Received: 27 April 2011; in revised form: 20 June 2011 / Accepted: 22 June 2011 / Published: 15 July 2011</div>\n\n<div class=\"belongsTo\">(This article belongs to the  Special Issue <a href=\"/journal/symmetry/special_issues/measures\">Symmetry Measures on Complex Networks</a>)</div>\n<div class=\"licenseText\">\n<em>This is an open access article distributed under the <a href=\"http://creativecommons.org/licenses/by/3.0/\" target=\"_blank\">\nCreative Commons Attribution License</a> which permits unrestricted use, distribution, \nand reproduction in any medium, provided the original work is properly cited.</em>\n</div>\n\n<div id=\"pdf_loaded\" style=\"display:none\">No</div>\n\n<div id=\"tabs\"  style=\"padding: 1em\">\n  <ul class=\"ui-tabs-nav\">\n   \t<li><a href=\"#tabs-0\">&nbsp;Abstract&nbsp;</a></li>\n   \t   \t<li><a href=\"#tabs-5\">PDF Full-Text</a></li>\n   \t   \t\n    <li><a href=\"#tabs-1\">\n    \t\tCitations to this Article\n\t    \t</a></li>\n    <li><a"], "copyright__copyright__copyright": ["2:12 CEST]\n\nExport to BibTeX |\nEndNote\n\n\nMDPI and ACS Style\n\nLevit, V.E.; Mandrescu, E. On Symmetry of Independence Polynomials. Symmetry 2011, 3, 472-486.\n\nAMA Style\n\nLevit VE, Mandrescu E. On Symmetry of Independence Polynomials. Symmetry. 2011; 3(3):472-486.\n\nChicago/Turabian Style\n\nLevit, Vadim E.; Mandrescu, Eugen. 2011. \"On Symmetry of Independence Polynomials.\" Symmetry 3, no. 3: 472-486.\n\nSymmetry EISSN 2073-8994 Published by MDPI AG, Basel, Switzerland RSS E-Mail Table of Contents Alert"]}