Inverse M-matrices completions of the n-chordal graph

Abstract

In this paper, the completion problems for chordal graphs and block graphs are discussed using graph theory. Based on the completion theorem for 1-chordal graph, we give the completion theorems for 2-chordal graph and 3-chordal graph, make the completion problem extend to n-chordal graph. We also give the definition of block graph and discuss the completion for 1-chordal block graph, 2-chordal block graph, and 3-chordal block graph. The corresponding algorithms that can be used to get the completions are also presented.

Keywords:

• n-Chordal graph
• Block graph
• Partial inverse M-matrix
• 1-Chordal graph
• 2-Chordal graph
• 3-Chordal graph