Characterizations of strongly chordal graphs.

*(English)*Zbl 0514.05048##### MSC:

05C75 | Structural characterization of families of graphs |

05C35 | Extremal problems in graph theory |

05C65 | Hypergraphs |

##### Keywords:

chordal graphs; forbidden induced subgraph characterization; totally balanced hypergraphs; polynomial algorithms; minimum weight domination; independent domination
Full Text:
DOI

##### References:

[1] | Anstee, R.P., Properites of (0,1)-matrices with no triangles, J. combin. theory, 29, A, 186-198, (1980) · Zbl 0519.05011 |

[2] | R.P. Anstee, Hypergraphs with no special cycles, submitted to Combinatorica. · Zbl 0526.05043 |

[3] | R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, submitted to J. of Algorithms. |

[4] | Booth, K.S., Dominating sets in chordal graphs, (July, 1980), Dept. of Computer Science, University of Waterloo, CS-80-34 |

[5] | G. Chang, Personal communications (1982) (to be included in his Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University). |

[6] | Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703 |

[7] | Farber, M., Applications of 1.p. duality to problems involving independence and domination, (), Technical report 81-13, (1981), Computing Science Department, Simon Fraser University |

[8] | M. Farber, Domination, independent domination, and duality in strongly chordal graphs, submitted to Discrete Applied Math. · Zbl 0531.05045 |

[9] | Gavril, F., The intersection graphs of subtrees of trees are exactly the chordal graphs, J. combin. theory, 16, B, 47-56, (1974) · Zbl 0266.05101 |

[10] | Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York, NY · Zbl 0541.05054 |

[11] | Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064 |

[12] | A.J. Hoffman, A.W.J. Kolen and M. Sakarovitch, Totally-balanced and greedy matrices, submitted to SIAM J. Algebraic Discrete Methods. · Zbl 0573.05041 |

[13] | LovĂˇsz, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001 |

[14] | Lubiw, A., Personal communication, (1981) |

[15] | Rose, D.J., Traingulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602 |

[16] | Chang, G.J.; Nemhauser, G.L., The k-domination and k-stability problems on graphs, () · Zbl 0576.05054 |

[17] | Iijima, K.; Shibata, Y., A bipartite representation of a triangulated graph and its chordality, (1979), Department of Computer Science, Gunma University, CS-79-1 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.