Name
Abstract | ||
|---|---|---|
We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has little impact on a class of graphs; it however makes a big difference in this case. We call the new class strongly chordal graphs with possible loops. When all vertices have loops, we recover the usual strongly chordal graphs; when all vertices are loopless, we obtain the usual chordal bigraphs. Moreover, there is a surprizing wealth of graphs in the new class that have loops at some vertices and not at others. These graphs also admit the elegant algorithms previously only applied in the extreme two cases. Formulated in the language of adjacency matrices, we study the class of symmetric 0, 1 matrices that admit a simultaneous row and column permutation avoiding the Gamma matrix [1 1 1 0]. We give ordering characterizations, matrix characterizations, and forbidden subgraph characterizations of the new class, and illustrate its usefulness by solving the minimum domination problem in this general context. This implies solutions of both the minimum dominating set in strongly chordal graphs and the minimum total dominating set in chordal bigraphs. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1316056 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
strongly chordal graph, totally balanced matrix, Gamma-free matrix, forbidden subgraph, domination, total domination | Journal | 35 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavol Hell | 1 | 2638 | 288.75 |
| César Hernández-Cruz | 2 | 33 | 10.41 |
| jing huang | 3 | 37 | 16.25 |
| Jephian C.-H. Lin | 4 | 0 | 0.34 |