Geodesic
A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube
Murali Krishna Srinivasan1
1Indian Institute of Technology, Bombay
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The number of spanning trees of a graph $G$ is called the complexity of $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))$.
DOI : 10.37236/2389
Classification : 05A15, 05C50, 05C05, 05E30
Mots-clés : spanning trees, Matrix-Tree theorem

Murali Krishna Srinivasan  1

1 Indian Institute of Technology, Bombay 
@article{10_37236_2389,
     author = {Murali Krishna Srinivasan},
     title = {A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {2},
     doi = {10.37236/2389},
     zbl = {1244.05019},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2389/}
}
TY  - JOUR
AU  - Murali Krishna Srinivasan
TI  - A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2389/
DO  - 10.37236/2389
ID  - 10_37236_2389
ER  - 
%0 Journal Article
%A Murali Krishna Srinivasan
%T A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2389/
%R 10.37236/2389
%F 10_37236_2389
Murali Krishna Srinivasan. A positive combinatorial formula for the complexity of the \(q\)-analog of the \(n\)-cube. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2389

Cité par Sources :