A Graph Polynomial Approach to Primitivity

详细信息    查看全文

• 作者：Francine Blanchet-Sadri (18)
  Michelle Bodnar (19)
  Nathan Fox (20)
  Joe Hidakatsu (19)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7810
• 期：1
• 页码：165-176
• 全文大小：239KB
• 参考文献：1. Blanchet-Sadri, F.: Primitive partial words. Discrete Applied Mathematics聽148, 195鈥?13 (2005) CrossRef
  2. Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton (2008)
  3. Blanchet-Sadri, F., Nikkel, J.: Computing primitively-rooted squares and runs in partial words (2012) (preprint)
  4. Brown, J.I., Hoshino, R.: On circulants uniquely characterized by their independence polynomials. Ars Combinatoria聽104, 363鈥?74 (2012)
  5. D枚m枚si, P., Horv谩th, S., Ito, M.: Context-Free Languages and Primitive Words. World Scientific (2011) (to appear)
  6. Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society聽16, 109鈥?14 (1965) CrossRef
  7. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford University Press (2008)
  8. Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997) CrossRef
  9. Makowsky, J.A.: From a zoo to a zoology: Towards a general study of graph polynomials. Theory of Computing Systems聽43, 542鈥?62 (2008) CrossRef
  10. Petersen, H.: On the language of primitive words. Theoretical Computer Science聽161, 141鈥?56 (1996) CrossRef
  11. Tittmann, P., Averbouch, I., Makowsky, J.: The enumeration of vertex induced subgraphs with respect to number of components. European Journal of Combinatorics聽32, 954鈥?74 (2010) CrossRef
  
• 作者单位：Francine Blanchet-Sadri (18)
  Michelle Bodnar (19)
  Nathan Fox (20)
  Joe Hidakatsu (19)
  
  18. Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC, 27402鈥?170, USA
  19. Department of Mathematics, University of Michigan, 530 Church Street, Ann Arbor, MI, 48109鈥?043, USA
  20. Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ, 08854鈥?019, USA
  
• ISSN：1611-3349

文摘

Recently, Tittmann et al. introduced the subgraph component polynomial and showed that its power for distinguishing graphs is quite different from the power of other graph polynomials that appear in the literature such as the matching polynomial, the Tutte polynomial, the characteristic polynomial, the chromatic polynomial, etc. The subgraph component polynomial enumerates vertex induced subgraphs in a given undirected graph with respect to the number of components. We show the use of the subgraph component polynomial to count the number of primitive partial words of a given length over an alphabet of a fixed size, which leads to a method for enumerating such partial words.