On the dependence polynomial of a graph

Qian J, Dress A, Wang Y (2007)
European Journal of Combinatorics 28(1): 337-346.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Qian, Jianguo; Dress, AndreasUniBi; Wang, Yan
Abstract / Bemerkung
The dependence polynomial P-G = P-G (z) of a graph G is defined by P-G (z) := Sigma(n)(i)(=0)(-1)(i)c(i)z(i) where c(i) = c(i) (G) is the number of complete subgraphs of G of cardinality i. It is clear that the complete subgraphs of G form a poset relative to subset inclusion. Using Mobius inversion, this yields various identities involving dependence polynomials implying in particular that the dependence polynomial of the line graph L(G) of G is determined uniquely by the (multiset of) vertex degrees of G and the number of triangles in G. Furthermore, the dependence polynomial of the complement of the line graph of G is closely related to the matching polynomial of G, one of the most 'prominent' polynomials studied in graph theory. (c) 2005 Elsevier Ltd. All rights reserved.
Erscheinungsjahr
2007
Zeitschriftentitel
European Journal of Combinatorics
Band
28
Ausgabe
1
Seite(n)
337-346
ISSN
0195-6698
Page URI
https://pub.uni-bielefeld.de/record/1597445

Zitieren

Qian J, Dress A, Wang Y. On the dependence polynomial of a graph. European Journal of Combinatorics. 2007;28(1):337-346.
Qian, J., Dress, A., & Wang, Y. (2007). On the dependence polynomial of a graph. European Journal of Combinatorics, 28(1), 337-346. https://doi.org/10.1016/j.ejc.2005.07.015
Qian, J., Dress, A., and Wang, Y. (2007). On the dependence polynomial of a graph. European Journal of Combinatorics 28, 337-346.
Qian, J., Dress, A., & Wang, Y., 2007. On the dependence polynomial of a graph. European Journal of Combinatorics, 28(1), p 337-346.
J. Qian, A. Dress, and Y. Wang, “On the dependence polynomial of a graph”, European Journal of Combinatorics, vol. 28, 2007, pp. 337-346.
Qian, J., Dress, A., Wang, Y.: On the dependence polynomial of a graph. European Journal of Combinatorics. 28, 337-346 (2007).
Qian, Jianguo, Dress, Andreas, and Wang, Yan. “On the dependence polynomial of a graph”. European Journal of Combinatorics 28.1 (2007): 337-346.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar