On minimal vertex separators of dually chordal graphs: properties and characterizations (Q1759837)

From MaRDI portal
Revision as of 19:56, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
scientific article
Language Label Description Also known as
English
On minimal vertex separators of dually chordal graphs: properties and characterizations
scientific article

    Statements

    On minimal vertex separators of dually chordal graphs: properties and characterizations (English)
    0 references
    0 references
    0 references
    22 November 2012
    0 references
    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.
    0 references
    0 references
    chordal
    0 references
    dually chordal
    0 references
    separator
    0 references
    tree
    0 references
    clique
    0 references
    neighborhood
    0 references

    Identifiers