On minimal vertex separators of dually chordal graphs: properties and characterizations
type: Item
instance of: scholarly article
title: On minimal vertex separators of dually chordal graphs: properties and characterizations
zbMATH Open document ID: 1259.05096
author: Pablo De Caria
author: M. Gutierrez
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
review text: A chord of a cycle is an edge joining two nonconsecutive vertices of the cycle. Chordal graphs are those without chordless cycles of length at least four. A vertex \(w\) is a maximum neighbor of \(v\) if \(N^2[v] \subset N[w]\). A linear ordering \(v_1,\dots,v_n\) of the vertices of \(G\) is a maximum neighborhood ordering of \(G\), if for \(i=1,\dots ,n\), \(v_i\) has a maximum neighbor in \(G[\{v_i,\dots ,v_n\}]\). Dually chordal graphs can be defined as those possessing a maximum neighborhood ordering. In this paper, two major characterizations of dually chordal graphs are given. Their first result states that a graph is dually chordal if and only if it possesses a spanning tree such that every minimal vertex separator induces a subtree. Their second result states that a graph is dually chordal if and only if the family of minimal vertex separator is Helly, its intersection graph is chordal and each of its members induces a connected subgraph.
reviewed by: Shinya Fujita
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6109909
zbMATH Keywords: chordal
zbMATH Keywords: dually chordal
zbMATH Keywords: separator
zbMATH Keywords: tree
zbMATH Keywords: clique
zbMATH Keywords: neighborhood
MaRDI profile type: Publication
full work available at URL: j.dam.2012.02.022
OpenAlex ID: W2152925324
cites work: Dually Chordal Graphs
cites work: On rigid circuit graphs
cites work: Characterizations of strongly chordal graphs
cites work: Algorithmic graph theory and perfect graphs
cites work: Triangulating Vertex-Colored Graphs
cites work: A Characterization of Soft Hypergraphs
cites work: Clique Graphs of Chordal and Path Graphs
cites work: Representations of chordal graphs as subtrees of a tree
DOI: 10.1016/J.DAM.2012.02.022
description: scientific article; zbMATH DE number 6109909