ICAR Research Data Repository for Knowledge Management
A positive combinatorial formula for the complexity of the q-analog of the n-cube
DSpace at IIT Bombay
View Archive Info| Field | Value | |
| Title |
A positive combinatorial formula for the complexity of the q-analog of the n-cube
|
|
| Creator |
SRINIVASAN, MK
|
|
| Description |
The number of spanning trees of a graph G is called the complexity of G and denoted c(G). A classical result in algebraic graph theory explicitly diagonalizes the Laplacian of the n-cube C(n) and yields, using the Matrix-Tree theorem, an explicit formula for c(C (n)). In this paper we explicitly block diagonalize the Laplacian of the q-analog C-q(n) of C(n) and use this, along with the Matrix-Tree theorem, to give a positive combinatorial formula for c(C-q(n)). We also explain how setting q = 1 in the formula for c(C-q(n)) recovers the formula for c(C(n)).
|
|
| Publisher |
ELECTRONIC JOURNAL OF COMBINATORICS
|
|
| Date |
2014-10-14T17:34:59Z
2014-10-14T17:34:59Z 2012 |
|
| Type |
Article
|
|
| Identifier |
ELECTRONIC JOURNAL OF COMBINATORICS, 19(2)
http://dspace.library.iitb.ac.in/jspui/handle/100/14581 |
|
| Language |
en
|
|