A matrix analysis of carrier posets of biconnected graphs
Author:
Peter W. Stephens a
| Affiliation: | a Department of Mathematics, U.C.S.D., La Jolla, CA |
DOI:
10.1080/03081089508818339
Publication Frequency:
8 issues per year
Subjects:
Algebra;
Fields & Rings;
Linear & Multilinear Algebra;
Numerical Algebra;
Vector & Tensor Analysis;
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
We define the Carrier Poset, (PG ≤ PG), for a biconnected simple graph G. The incidence algebra A(PG), for this poset is considered by studying a certain class of functions f called broken cycle content functions. We describe matrices Mj of these functions as elements of A(PG) with respect to a particular linear order on PG. For any such broken cycle content matrix for a full span chain. with the pre-cut and post-cut properties. in (PG ≤ PG), we show that there is an associated submatrix of Mp which is upper triangular weakly decreasing in rows, and weakly increasing in columns. we study full span bicomponent trees for biconnected simple graphs and interpret our results on chains in terms of these structures. These results suggest a general mathematical view of why certain classical optimal graph algorithms always seem to work in regions of PG associates with such full span chains.
|
| view references (14) |

Download Citation


CiteULike
Del.icio.us
BibSonomy
Connotea