On strictly chordality-k graphs

DOI10.1016/J.DAM.2018.06.028MaRDI QIDQ2181248zbMATH OpenOpenAlexFDO

Authors S. Dhanalakshmi, N. Sadagopan

Publication date 18 May 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.00359

zbMATH Keywords

treewidthminimal vertex separator

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38)

Abstract: Strictly Chordality-k graphs (SC_k graphs) are graphs which are either cycle free or every induced cycle is exactly k, for some fixed k, k geq 3. Note that k = 3 and k = 4 are precisely the Chordal graphs and Chordal Bipartite graphs, respectively. In this paper, we initiate a structural and an algorithmic study of SCk, k geq 5 graphs.

Recommendations

• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• A Dirac-type characterization of \(k\)-chordal graphs
• A \(k\)-partite generalization of chordal bipartite graphs
• Strengthening strongly chordal graphs
• Characterizing k-chordal unichord-free graphs

Cites work

• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906530 (Why is no real title available?)
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 512817 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Characterizations of totally balanced matrices
• Detecting fixed patterns in chordal graphs in polynomial time
• Dominating Sets in Chordal Graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• Incidence matrices and interval graphs
• Join colourings of chordal graphs
• On rigid circuit graphs
• On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The complexity of generalized clique covering
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(10)

• scientific article; zbMATH DE number 7085004 (Why is no real title available?)
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• On 3-degree 4-chordal graphs
• Characterizing k-chordal unichord-free graphs
• Necessary edges in k-chordalisations of graphs
• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• A \(k\)-partite generalization of chordal bipartite graphs
• On strongly chordal graphs that are not leaf powers
• Semi-strict chordality of digraphs

This page was built for publication: On strictly chordality-\(k\) graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2181248)