×

The diameter of the acyclic Birkhoff polytope. (English) Zbl 1213.05163

Summary: We give an interpretation of vertices and edges of the acyclic Birkhoff polytope, \({\mathfrak I}_n= \Omega_n(T)\), where \(T\) is a tree with \(n\) vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph \(G({\mathfrak I}_n)\).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05A15 Exact enumeration problems, generating functions
15B51 Stochastic matrices
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Birkhoff, G., Tres observaciones sobre el algebra lineal, Univ. Nac. de Tucumán Rev. Sér. A, 5, 147-151 (1946)
[2] Brualdi, R., Convex polytopes of permutation invariant doubly stochastic matrices, J. Combin. Theory, 23, 58-67 (1977) · Zbl 0375.05010
[3] Brualdi, R.; Gibson, P., Convex polyhedra of doubly stochastic matrices, I. Applications of the permanent function, J. Combin. Theory, 22, 194-230 (1977) · Zbl 0355.15013
[4] Brualdi, R.; Gibson, P., Convex polyhedra of doubly stochastic matrices, II. Graph of \(\Omega_n\), J. Combin. Theory, 22, 175-198 (1977) · Zbl 0351.05130
[5] Brualdi, R.; Gibson, P., Convex polyhedra of doubly stochastic matrices, III. Affine and combinatorial properties of \(\Omega_n\), J. Combin. Theory, 22, 338-351 (1977) · Zbl 0368.15010
[6] Brualdi, R.; Gibson, P., Convex polyhedra of doubly stochastic matrices - IV, Linear Algebra Appl., 15, 153-172 (1976) · Zbl 0351.15014
[7] Brualdi, R.; Ryser, H., Combinatorial Matrix Theory. Combinatorial Matrix Theory, Encycl. of Math. and its Appl. (1991), Cambridge University Press
[8] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland: North-Holland New York · Zbl 1134.05001
[9] Chartrand, G.; Haynes, T.; Henning, M.; Zhang, P., Stratification and domination in graphs, Discrete. Math., 272, 2-3, 171-185 (2003) · Zbl 1028.05074
[10] Dahl, G., Tridiagonal doubly stochastic matrices, Linear Algebra Appl., 390, 197-208 (2004) · Zbl 1060.15022
[11] C.M. da Fonseca, E. Marques de Sá, Fibonacci numbers, alternating parity sequences and faces of the tridiagonal Birkhoff polytope, Discrete Math. (2007), doi:10.1016/j.disc.2007.03.077; C.M. da Fonseca, E. Marques de Sá, Fibonacci numbers, alternating parity sequences and faces of the tridiagonal Birkhoff polytope, Discrete Math. (2007), doi:10.1016/j.disc.2007.03.077
[12] Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer New York · Zbl 0968.05002
[13] Grünbaum, B., Convex Polytopes (2003), Springer-Verlag: Springer-Verlag New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.