| Title:
|
Several results on chordal bipartite graphs (English) |
| Author:
|
Bakonyi, Mihály |
| Author:
|
Bono, Aaron |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
47 |
| Issue:
|
4 |
| Year:
|
1997 |
| Pages:
|
577-583 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that, to any vertex of a chordal bipartite graph an edge may be added such that the chordality is maintained. (English) |
| MSC:
|
05C38 |
| MSC:
|
05C50 |
| MSC:
|
05C75 |
| MSC:
|
15A06 |
| idZBL:
|
Zbl 0898.05043 |
| idMR:
|
MR1479305 |
| . |
| Date available:
|
2009-09-24T10:08:29Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127379 |
| . |
| Reference:
|
[1] M. Bakonyi: Completion of Partial Operator Matrices.Thesis, The College of William and Mary, Williamsburg, Virginia, August, 1992. |
| Reference:
|
[2] M. Bakonyi, T. Constantinescu: Inheritance Principles for Chordal Graphs.Linear Algebra Appl. 148 (1991), 125–143. MR 1090757 |
| Reference:
|
[3] N. Cohen, C.R. Johnson, L. Rodman, H. Woerdeman: Ranks of Completions of Partial Matrices, in: The Gohberg Anniversary Collection, Vol I (Eds. H. Dym. S. Goldberg, M.A. Kaashoek and P. Lancaster).Operator Theory: Adv. Appl., OT 40, Birhäuser Verlag, Basel, 1989, pp. 165–185. MR 1038313 |
| Reference:
|
[4] M.C. Golumbic: Algorithmic Graph Theory and the Perfect Graph.Academic Press, New York, 1980. MR 0562306 |
| Reference:
|
[5] M.C. Golumbic, C.F. Goss: Perfect Elimination and Chordal Bipartite Graphs.J. Graph Theory 2 (1978), 155–163. MR 0493395, 10.1002/jgt.3190020209 |
| Reference:
|
[6] R. Grone, C.R. Johnson, E. Sa, H. Wolkowitz: Positive Definite Completions of Partial Hermitian Matrices.Linear Algebra and Appl. 58 (1984), 102–124. MR 0739282 |
| Reference:
|
[7] C.R. Johnson, L. Rodman: Completion of Partial Matrices to Contractions.J. Functional Analysis 69 (1986), 260–267. MR 0865223 |
| Reference:
|
[8] D.J. Rose: Triangulated Graphs and the Elimination Process.J. Math. Anal. Appl. 32 (1970), 597–609. Zbl 0216.02602, MR 0270957, 10.1016/0022-247X(70)90282-9 |
| Reference:
|
[9] D.J. Rose, R.E. Tarjan, G.S. Leuker: Algorithmic Aspects of Vertex Eliminations on Directed Graphs.SIAM J. Appl. Math. 34 (1978), 176–197. MR 0488988, 10.1137/0134014 |
| . |
