Abstract
Negami and Kawagoe has already defined a polynomial \(\tilde f\left( G \right)\) associated with each graphG as what discriminates graphs more finely than the polynomialf(G) defined by Negami and the Tutte polynomial. In this paper, we shall show that the polynomial \(\tilde f\left( G \right)\) includes potentially the generating function counting the independent sets and the degree sequence of a graphG, which cannot be recognized from f(G) in general, and discuss on \(\tilde f\left( T \right)\) of treesT with observations by computer experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
de la Harpe, P., Jones, V.F.R.: Graph invariants related to statistical mechanical models: examples and problems. J. Comb. Theory. Ser.B 57, 207–227 (1993)
Kauffman, L.H.: Knots and Physics (World Scientific Publishing, Singapore, New Jersey, London, Hong Kong, 1991)
Negami, S.: Polynomial invariants of graphs. Trans. Amer. Math. Soc.299, 601–622 (1987)
Negami, S., Kawagoe, K.: Polynomial invariants of graphs with state models. Discrete Appl. Math.56, 323–331 (1995)
Oxley, J.G.: A note on Negami's polynomial invariants for graphs. Discrete Math.76, 279–281 (1989)
Tutte, W.T.: Graph theory, Encyclopedia of Mathematics, vol. 21 (Addison-Wesley, 1984)
Welsh, D.J.A.: Matroid theory (Academic Press, London, New York, San Francisco, 1976)
Whitney, H.: 2-isomorphic graphs. Amer. J. Math.55, 245–254 (1933)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Negami, S., Ota, K. Polynomial invariants of graphs II. Graphs and Combinatorics 12, 189–198 (1996). https://doi.org/10.1007/BF01858453
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01858453